注意

Pythonはpypyを使ってください

問題

長さ NN の数列 AA が与えられます。 QQ 回のクエリが与えられるので順に処理してください。

  • 1 L R: AL,,ARA_L, \ldots, A_R 内での最頻値のうち最小の値を出力する
  • 2 k X: AkA_kXXを代入する

最頻値は、その区間で最も多く出現する数値です。

制約

  • 1N1061 \leqq N \leqq 10^6
  • 1Ai,X1031 \leqq A_i, X \leqq 10^3
  • 1Q3×1031 \leqq Q \leqq 3 \times 10^3
  • 1LRN1 \leqq L \leqq R \leqq N
  • 1kN1 \leqq k \leqq N

入力

NN
A1    ANA_1 \; \ldots \; A_N
QQ
Query1\text{Query}_1
\vdots
QueryQ\text{Query}_Q

各クエリは以下の形式で与えられる。

1  L  R1 \; L \; R

2  k  X2 \; k \; X

出力

各タイプ1のクエリに対して答えを1行で出力してください。

入力例1

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

出力例1

4
1
1

1つめのクエリの部分配列は(1,4,4)(1, 4, 4)なので44が最頻値です。

2つめのクエリの部分配列は(1,4,4,1)(1, 4, 4, 1)1,41,4が同数ありますが、小さい方の11が答えです。

3つめのクエリで数列AA(1,1,4,1,3)(1, 1, 4, 1, 3)となります。

最後は部分配列(1,1,4)(1, 1, 4)なので11が最頻値となります。

入力例2

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

出力例2

3
1
10
4

Submit


Go (1.21)