Problem Description

You are given a sequence of length $ N $: $A_0, A_1, \cdots, A_{N-1}$. Answer $ Q $ queries. Specifically, for query $ i $ ($0 \leq i \leq Q-1$), you are given integers $ T_i, X_i, Y_i $, and you need to do the following:

• When $ T_i = 0 $: Replace $ A_{X_i} $ with $ Y_i $.
• When $ T_i = 1 $: Find the number of pairs of integers $ l, r $ ($X_i \leq l < r \leq Y_i$) that satisfy the condition:
• All elements in the subsequence $A_{l}, A_{l+1}, \cdots, A_{r-1}$ are distinct.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ A_0 $ $ A_1 $ $\cdots$ $ A_{N-1} $ $ T_0 $ $ X_0 $ $ Y_0 $ $ T_1 $ $ X_1 $ $ Y_1 $ $\vdots$ $ T_{Q-1} $ $ X_{Q-1} $ $ Y_{Q-1} $

Output Format

For each query where $ T_i = 1 $, output the answer in the order the queries are given, one per line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

8
15
5

Sample Input #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

Sample Output #2

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

Notes/Hints

Constraints

• $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 $)
• There is at least one $ i $ such that $ T_i = 1 $.
• All values inputted are integers.

Sample Explanation 1

Consider query $ 4 $ as an example. When this query is given, $ A = (0, 1, 4, 3, 4) $. The pairs $ l, r $ that satisfy the condition are $ (l, r) = (2, 3), (2, 4), (3, 4), (3, 5), (4, 5) $, totaling 5 pairs.

见题面 Input 部分

见题面 Output 部分