005 - Count2

問題

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

クエリ１

1 $x$ $k$

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

クエリ２

2 $k$

数列$A$の中に存在する$k$以下の個数を出力せよ。

入力

$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

出力例１

5
10
3

1,2つめのクエリはそれぞれ
$(3,1,4,1,5,9,2,6,5,3)$の中の$3$以下の個数は$5$
$(3,1,4,1,5,9,2,6,5,3)$の中の$9$以下の個数は$9$
となります。
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$となります。

入力例２

5
1 5 3 9 1 
3
2 4
1 3 3
1 1 3    

出力例２

3