Birthday#3205
Stan received a magic array from Stewie for his birthday. This array can do two things: change any element, and answer queries of the form: "how many different numbers are there in the interval from to ?"
Stan is quite impressed by the gift, but he is also suspicious, as Stewie has a reputation for playing tricks. At first glance, everything seemed fine: Stan performed several simple operations, and the array returned all correct answers.
To fully test the magic array and dispel any doubts, Stan asks for your help: he will perform a sequence of operations, and you must provide the correct answers so Stan can verify whether the array is truly magic.
The first line contains two integers and (1 \leq n, m \leq 50000). The second line contains numbers — the initial contents of the array. The following lines describe the operations:
Update operation: , where (0 \leq x < n) is the index in the array to change, and is the new value.
Query operation: , where (0 \leq x \leq y < n) are the bounds of the interval in which you need to count the number of distinct numbers.
All numbers in the array are non-negative integers not exceeding 10^9.
For each query of the form "", print the result on a separate line, as calculated by Stan's magic array.
Example 1