Integer Sequence Operations and Distinct Count Query

You are given an integer sequence \(a_1, a_2, \dots, a_n\) and \(m\) operations. For each operation, you are given three integers \(l, r, x\). The operation consists of two parts:

Modification:
If \(l \le r\), sort the subarray \(a_l, a_{l+1}, \dots, a_r\) in ascending order; otherwise (if \(l > r\)), sort the subarray \(a_r, a_{r+1}, \dots, a_l\) in descending order.

Query:
After the modification, compute the number of distinct values among the first \(x\) elements of the sequence, i.e. in \(a_1, a_2, \dots, a_x\).

Process all \(m\) operations sequentially and output the answer for each query.

inputFormat

The first line of input contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5) \) representing the number of elements in the sequence and the number of operations.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces.

Each of the next \(m\) lines contains three integers \(l, r, x\) \( (1 \leq l, r, x \leq n) \), representing one operation.

outputFormat

For each operation, after performing the modification on the sequence, print a single integer: the number of distinct values in the first \(x\) elements of the current sequence.

sample

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

3
4
4