長さ $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-indexed とする。

入力

1 行目には数列の長さ $N$ が与えられる ($1 \le N \le 100\,000$)。

2 行目には $A_1, A_2, \ldots, A_N$ が与えられる ($1 \le A_i \le 10^9$)。

3 行目にはクエリの個数 $M$ が与えられる ($1 \le M \le 100\,000$)。

次の $M$ 行には各クエリが 1 行ずつ記述される。

出力

タイプ 2 のクエリごとに、答えを 1 行ずつ順に出力せよ。

入出力例

入力例 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