問題文

長さ N の数列 A_0,A_1,\cdots,A_{N-1} があります。 Q 個のクエリに答えてください。 具体的には、クエリ i (0 \leq i \leq Q-1) では整数 T_i,X_i,Y_i が与えられるので、以下のことをしてください。

• T_i=0 の時: A_{X_i} を Y_i で置き換える。
• T_i=1 の時: 次の条件をみたす整数の組 l,r (X_i \leq l < r \leq Y_i) の個数を答える。
  • A_{l},A_{l+1},\cdots,A_{r-1} が全て異なる。

制約

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 5 \times 10^5
• 0 \leq A_i \leq N-1
• 0 \leq T_i \leq 1
• 0 \leq X_i \leq N-1,\ 0 \leq Y_i \leq N-1 (T_i=0)
• 0 \leq X_i < Y_i \leq N (T_i=1)
• T_i=1 をみたす i が少なくとも 1 つ存在する。
• 入力される値はすべて整数である。

入力例 1

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

出力例 1

8
15
5

例としてクエリ 4 を考えます。 このクエリが与えられた時、A=(0,1,4,3,4) です。 また、条件をみたす l,r の組は、(l,r)=(2,3),(2,4),(3,4),(3,5),(4,5) の 5 個です。

入力例 2

30 30
14 24 18 7 20 10 0 27 27 29 27 20 23 29 27 0 11 10 0 12 19 7 21 12 11 7 27 11 21 0
1 6 21
1 27 29
0 23 21
1 1 5
0 3 24
1 3 6
1 9 16
1 16 26
1 0 11
0 29 27
0 25 29
0 4 24
1 10 23
1 18 24
0 22 14
0 13 10
1 2 29
0 7 12
0 27 14
1 18 20
0 23 7
0 15 20
1 1 24
0 24 7
0 24 20
1 7 16
0 15 27
0 23 10
1 11 13
1 4 8

出力例 2

53
3
10
6
23
34
31
57
16
116
3
94
28
3
10