長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。以下のクエリを実行するプログラムを作成せよ。

• 1 i j k: $A_i, A_{i+1}, \ldots, A_j$ からなる部分列内で $k$ より大きい要素の個数を出力する。
• 2 i k: $A_i$ を $k$ に変更する。

数列のインデックスは 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$ 行にはそれぞれクエリ $i, j, k$ が与えられる $(1 \le i \le j \le N, 1 \le k \le 10^9)$。

出力

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

入出力例

入力例 1

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

出力例 1

2
1
4