Problem Description

Xiao D has $n$ std::queue<int> objects, numbered from $1$ to $n$.

Xiao D has a different level of liking for each queue. If a queue that he does not like much uses too much memory, Xiao D will be unhappy.

More specifically, if the size() of the $i$-th queue is greater than $a_i$, Xiao D will keep calling pop() on this queue until its size() becomes less than or equal to $a_i$.

Now all these queues are empty. Xiao D thinks this is too boring, so he decides to perform some operations.

Each operation can be described by l r x, meaning that for all queues with indices in $[l, r]$, perform push(x). Of course, after each operation ends, Xiao D will use the method mentioned above to prevent these queues from using too much memory.

Xiao D's queues are magical, so he can perform each operation in $O(1)$ time.

He believes everyone else's queues can do it too, so Xiao D made this problem to give everyone easy points.

To prove that you really performed these operations, after each operation you need to output the number of distinct values that are still present in the queues.

Input Format

The first line contains two positive integers $n, m$, representing the number of queues and the number of operations.

The second line contains $n$ positive integers, where the $i$-th one is $a_i$.

The next $m$ lines each contain three positive integers l r x, where the $i$-th line describes the $i$-th operation.

Output Format

Output $m$ lines in total. Each line contains one non-negative integer, representing the number of distinct values across all queues after the $i$-th operation ends.

3 3
1 2 3
1 2 1
2 3 2
1 3 3

1
2
2

Hint

Sample Explanation

After the first operation, the queues become $\{1\}\{1\}\{\}$, and the values still in the queues are $1$, so there is $1$ distinct value.

After the second operation, the queues become $\{1\}\{1,2\}\{2\}$, and the values still in the queues are $1, 2$, so there are $2$ distinct values.

After the third operation, the queues become $\{3\}\{2,3\}\{2,3\}$, and the values still in the queues are $2, 3$, so there are $2$ distinct values.

Constraints

For all data, $n, m, a_i, x \leq 10^5$, and $l \leq r$.

There are $20$ test points in total, each worth $5$ points. The $k$-th test point satisfies $n, m, a_i, x \leq 5000k$.

In particular, the following test points satisfy some special properties:

Test point $5$: $a_i = 1$;
Test point $7$: $a_i = 2$;
Test point $9$: $a_i = 10$;
Test point $11$: $a_i \leq 10$;
Test points $13, 15$: $\sum a_i \leq 10^6$.

For each test point, you must pass all testdata that meets the constraints and properties of that point to obtain the score for that point.

Translated by ChatGPT 5