長さ $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 から始まるものとします。

入力

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
2
2
3