给定一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$。请编写一个程序处理以下查询：

• 1 i v：将 $A_i$ 修改为 $v$。（$1 \le i \le N$，$1 \le v \le 10^9$）
• 2 i j：输出 $A_i, A_{i+1}, \ldots, A_j$ 中值最小的元素的索引。如果有多个这样的元素，则输出索引最小的一个。（$1 \le i \le j \le N$，$1 \le v \le 10^9$）

序列的索引从 1 开始。

输入格式

第一行包含序列的长度 $N$。（$1 \le N \le 100{,}000$）

第二行包含 $A_1, A_2, \ldots, A_N$。（$1 \le A_i \le 10^9$）

第三行包含查询的个数 $M$。（$1 \le M \le 100{,}000$）

接下来 $M$ 行，每行给出一个查询。

输出格式

对于每个类型 2 的查询，按顺序每行输出一个答案。

样例

输入格式 1

5
5 4 3 2 1
6
2 1 3
2 1 4
1 5 3
2 3 5
1 4 3
2 3 5

输出格式 1

3
4
4
3