Distinct Elements Query

You are given an array of n non-negative integers. You need to process q queries on the array. There are two types of queries:

• Update Query: 1 i y — update the i-th element (1-indexed) of the array to the value y, i.e. set \(a[i]=y\).
• Distinct Query: 2 l r — count the number of distinct integers in the subarray from index l to r (inclusive).

More formally, if the array is \(a_1, a_2, \ldots, a_n\) and a query asks for the range \([l, r]\), you need to compute the cardinality of the set \(\{a_l, a_{l+1}, \dots, a_r\}\), i.e. \(|\{a_l, a_{l+1}, \dots, a_r\}|\).

The queries are processed sequentially and update queries affect subsequent queries. It is recommended to implement an efficient solution (for example, using a segment tree) to handle the queries.

inputFormat

The input is given via stdin in the following format:

n q
a1 a2 ... an
query1
query2
...
queryq

Here, the first line contains two integers \(n\) and \(q\) representing the number of elements in the array and the number of queries, respectively. The second line contains \(n\) non-negative integers (the elements of the array). Each of the following \(q\) lines contains a query in one of the following formats:

• 1 i y — update the i-th element to y (1-indexed).
• 2 l r — output the number of distinct integers in the subarray from l to r (inclusive).

outputFormat

For each distinct query (query of type 2), print the number of distinct integers in the corresponding subarray on a separate line to stdout.

## sample

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

3
4
3

</p>