Exotic Queries
Contest: Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
Difficulty rating: 2300
Tags: data structures, implementation, sortings

AquaMoon gives RiverHamster a sequence of integers $$$a_1,a_2,\dots,a_n$$$, and RiverHamster gives you $$$q$$$ queries. Each query is expressed by two integers $$$l$$$ and $$$r$$$.

For each query independently, you can take any continuous segment of the sequence and subtract an identical non-negative value from all the numbers of this segment. You can do so multiple (possibly, zero) times. However, you may not choose two intersecting segments which are not included in one another. Your goal is to convert to $$$0$$$ all numbers whose initial value was within the range $$$[l, r]$$$. You must do so in the minimum number of operations.

Please note that the queries are independent, the numbers in the array are restored to their initial values between the queries.

Formally, for each query, you are to find the smallest $$$m$$$ such that there exists a sequence $$$\{(x_j,y_j,z_j)\}_{j=1}^{m}$$$ satisfying the following conditions:

- for any $$$1 \le j \leq m$$$, $$$z_j \ge 0$$$ and $$$1 \le x_j \le y_j \leq n$$$ (here $$$[x_j, y_j]$$$ correspond to the segment of the sequence);
- for any $$$1 \le j < k \le m$$$, it is true that $$$[x_j,y_j]\subseteq[x_{k},y_{k}]$$$, or $$$[x_k,y_k]\subseteq[x_{j},y_{j}]$$$, or $$$[x_j,y_j]\cap[x_{k},y_{k}]=\varnothing$$$;
- for any $$$1 \le i \le n$$$, such that $$$l \le a_i \leq r$$$, it is true that $$$$$${\large a_i = \sum\limits_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j. }$$$$$$

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le 10^6$$$).

The second line contains $$$n$$$ integers integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\le l\le r\le n$$$), representing a query.

Output format:
For each query, output the answer for this query on a separate line.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, consider the second query, when $$$l = 2$$$, $$$r = 2$$$. The elements to be manipulated are $$$[a_3, a_5, a_{10}] = [2, 2, 2]$$$. It is sufficient to apply the operation sequence $$$\{(2, 10, 2)\}$$$.

Consider the fourth query, when $$$l = 2$$$, $$$r = 3$$$. The elements to be manipulated are $$$[a_3, a_4, a_5, a_7, a_{10}] = [2, 3, 2, 3, 2]$$$. It is sufficient to apply the operation sequence $$$\{(1, 10, 2), (4, 4, 1), (7, 7, 1)\}$$$.

In the second test case, note that the operation sequence $$$\{(1, 2, 1), (2, 3, 2)\}$$$ is invalid because the two segments intersect but neither is contained inside the other.

Example input:
10 8
1 6 2 3 2 6 3 10 1 2
1 10
2 2
3 3
2 3
1 3
3 6
4 6
5 5

Example output:
8
1
1
3
5
3
1
0

Example input:
3 1
1 3 2
1 3

Example output:
3

Editorial:
Hint: The final solution is irrelevant to Cartesian trees.
First, we consider only the sequence of elements to be manipulated. We claim that it is optimal to operate on the whole sequence so that the minimum elements are all decreased to $$$0$$$, and then solve the problem on the segments separated by the $$$0$$$s recursively.
A straightforward corollary of the claim is that two equal elements between which there are no smaller elements are handled in a single operation, so the final answer is $$$\ell$$$ (the number of elements to be manipulated) minus the number of such adjacent pairs.
Proof: Define $$$S(l, r)$$$ to be the answer for the segment $$$[l, r]$$$. Do induction on the length of the segment. If the first operation does not manipulate the whole segment, the segment will be separated into several independent parts by the first operation, for the non-inclusive operations cannot intersect, and the final answer, which is the sum of $$$S$$$ of the parts, will not be less than the initial answer according to the corollary, for some of the equal pairs are separated.
Now the original problem is converted into a data structure task. Consider all adjacent equal pairs $$$(l, r)$$$, and $$$m$$$ is the minimum element between $$$(l, r)$$$. $$$(l, r)$$$ decrease the answer if and only if $$$m < L \le a_l = a_r \le R$$$, which can be easily calculated with a segment tree and sweeping lines.