There are bells arranged in a line, labelled to . The bell has a frequency of Hz . There are operations to perform.
There are two types of operations:
1 i fReplace the bell with one with a frequency of Hz.
2 l rOutput the number of distinct frequencies between the and bell (inclusive).
There will be at most distinct frequencies at a time.
Fast input may be required.
For 10% of the points, .
For 90% of the points, .
The first line contains two space separated integers, , respectively the number of bells and the number of queries.
The next line contains space separated integers, the frequency of the bells.
The next lines each contain a query in the format described above.
Output a single integer on its own line for each type 2 query.
Sample Input 1
6 3 1 2 1 4 4 2 2 1 6 1 2 1 2 1 3
Sample Output 1
Sample Output 1 Explanation
In the beginning, there are only 3 distinct frequencies which the bells have, 1 Hz, 2 Hz, and 4 Hz. After switching the second bell with one with a frequency of 1 Hz. There is only one distinct frequency among the first 3 bells.