ADAUNIQ - Ada and Unique Vegetable


Ada the Ladybug is cultivating vegetables. She has a long furrow full of different kinds of it and she wants to know the number of unique vegetables on a segment of the furrow. As the cultivation is a dynamic process, a kind (on a single position) might become another kind during this process.

Given furrow and a few updates, can you answer questions asking about number of unique kinds of vegetable on a segment?

Input

The first line contains 1 ≤ N, Q ≤ 2*105 , length of furrow and number of queries.

Next line contains N integers 0 ≤ Ai ≤ 2*105, the kind of ith vegetable

Each of following Q lines contains one of the following kinds of query:

1 I V: The vegetable on index 0 ≤ I < N, will be changed to kind 0 ≤ A ≤ 2*105

2 L R: 0 ≤ L ≤ R < N , the index of left/right bound of segment for which you want to know the number of unique kinds.

Output

For each query of second kind, print the number of unique kinds of vegetable.

Example Input

8 8
1 2 3 3 1 2 3 3
2 1 3
2 0 3 
2 0 7
1 3 4
1 7 0
2 1 3
2 0 3 
2 0 7

Example Output

1
2
0
3
4
2

hide comments
swapnil_007: 2017-12-14 22:37:52

Last edit: 2017-12-15 19:14:58
morass: 2017-11-01 11:48:22

@tutis: Not this is correct - but I guess you found out, as you already have AC ^_^ Have Nice Day!

tutis: 2017-10-31 18:26:17

Is example output correct for that example input? Because i think the output should be: 2 3 3 3 4 5.

morass: 2017-02-24 22:44:00

@abdou_93: What does it mean? :O I guess it is between 0 and 2*10^5 (so any number is possible - for update queries)

abdou_93: 2017-02-24 19:46:51

what's the expected number of update?

morass: 2017-02-24 09:32:42

@Bhuvnesh Jain: Good day to you. Judge solution is offline :)

Bhuvnesh Jain: 2017-02-24 06:43:55

Is the intended solution online or offline?


Added by:Morass
Date:2017-02-23
Time limit:8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All