There are $N$ $(1\le N\le 100000)$ bells arranged in a line, labelled $1$ to $N$. The $i^{\text{th}}$ bell has a frequency of $f_i$ Hz $(1\le f_i\le {10}^8)$. There are $Q$ $(1\le Q\le 50000)$ operations to perform.

There are two types of operations:

• 1 i f Replace the $i^{\text{th}}$ bell with one with a frequency of $f$ Hz.
• 2 l r Output the number of distinct frequencies between the $l^{\text{th}}$ and $r^{\text{th}}$ bell (inclusive).

There will be at most $1000$ distinct frequencies at a time.

Fast input may be required.

Constraints

For 10% of the points, $1\le N,Q\le 100$.

For 90% of the points, $1\le N\le 100000,1\le Q\le 50000$.

Input Specification

The first line contains two space separated integers, $N$ $Q$, respectively the number of bells and the number of queries.

The next line contains $N$ space separated integers, the frequency of the bells.

The next $Q$ lines each contain a query in the format described above.

Output Specification

Output a single integer on its own line for each type 2 query.

Sample Input

6 3
1 2 1 4 4 2
2 1 6
1 2 1
2 1 3

Sample Output

3
1

Explanation for Sample Output

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.