006 - Kth Smallest2

問題

数列$A$が与えられる。以下のクエリを処理せよ。

クエリ１

1 $x$ $k$

$A$の$x$番目の値を$k$に変更する。

クエリ２

2 $x$

数列$A$の中で$x$番目に小さい数を出力せよ。

入力

$N$
$A_1$ $A_2$ ... $A_N$
$Q$
$Query1$
$Query2$
 :
$QueryQ$

出力

クエリ2の結果を改行区切りで出力せよ。

制約

$1 \leq N,Q \leq 10^6$

$0 \leq A_i \leq 10^9(1 \leq i \leq N)$

$0 \leq k \leq 10^9$

$1 \leq x \leq N$

クエリ2は必ず存在する

入力はすべて整数

入出力

入力例１

10
3 1 4 1 5 9 2 6 5 3
5
2 3
2 9
1 2 4
1 4 4
2 3

出力例１

2
6
3

1,2つめのクエリはそれぞれ
$(3,1,4,1,5,9,2,6,5,3)$の$3$番目に小さい数は$2$
$(3,1,4,1,5,9,2,6,5,3)$の$9$番目に小さい数は$6$
となります。
3,4つめのクエリ後は$A$は$(3,10,4,4,5,9,2,6,5,3)$となります。
5つめのクエリは$(3,4,4,4,5,9,2,6,5,3)$の$3$番目に小さい数は$3$となります。

入力例２

9
2 1 1 6 9 5 4 2 3 
8
1 5 7
2 4
2 5
1 3 3
2 8
2 2
2 9
1 5 5    

出力例２

2
3
6
2
7