# Sequence Master codechef solution- Given is a sequence AA of length NN. Define f(i,j)f(i,j) to be the number of distinct elements in Ai,Ai+1,…,AjAi,Ai+1,…,Aj. You need to process QQ queries of the following two types: 1 x y1 x y — set Ax=yAx=y. 2 k2 k — print ∑i=1k∑j=ikf(i,j)∑i=1k∑j=ikf(i,j).

## Sequence Master solution codechef

Given is a sequence AA of length NN.

Define f(i,j)f(i,j) to be the number of distinct elements in Ai,Ai+1,,AjAi,Ai+1,…,Aj.

You need to process QQ queries of the following two types:

• 1 x y1 x y — set Ax=yAx=y.
• 2 k2 k — print i=1kj=ikf(i,j)∑i=1k∑j=ikf(i,j).

### Input Format

• The first line of input contains two integers NN and QQ — the size of the array and the number of queries.
• The second line of input contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.
• Then, QQ lines follow, describing queries in the format given in the statement.

### Output Format

For each type 22 query, print the answer to it on a new line.

### Constraints

• 1N,Q21051≤N,Q≤2⋅105
• 1AiN1≤Ai≤N
• 1x,yN1≤x,y≤N
• 1kN1≤k≤N

• Subtask 1 (20 points): No type 11 queries
• Subtask 2 (80 points): Original constraints

### Sample Input 1

3 2
1 2 2
2 2
2 3


### Sample Output 1

4
8


### Explanation

Test Case 11: The answer is f(1,1)+f(1,2)+f(2,2)=1+2+1=4f(1,1)+f(1,2)+f(2,2)=1+2+1=4.

Test Case 22: The answer is f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8f(1,1)+f(1,2)+f(1,3)+f(2,2)+f(2,3)+f(3,3)=1+2+2+1+1+1=8.

### Sample Input 2

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


### Sample Output 2

35
8
17
31