P7416 [USACO21FEB] No Time to Dry P

Bessie recently received a set of paints, and she wants to paint the fence at one end of her pasture. The fence consists of $N$ small segments, each $1$ meter long ($1\le N\le 2\cdot 10^5$). Bessie can use $N$ different colors, labeled from $1$ to $N$ from light to dark ($1$ is very light, and $N$ is very dark). Thus, she can describe the desired color for each fence segment with an integer array of length $N$. At the beginning, all fence segments are unpainted. In one stroke, Bessie can paint any number of consecutive segments with the same color, as long as she does not paint a lighter color over a darker color (she may only use darker colors to cover lighter colors). For example, an unpainted fence of length $4$ can be painted as follows: ``` 0000 -> 1110 -> 1122 -> 1332 ``` Unfortunately, Bessie does not have enough time to wait for the paint to dry. Therefore, she thinks she may need to give up painting some segments of the fence. Now, she is considering $Q$ candidate intervals ($1\le Q\le 2\cdot 10^5$). Each interval is given by two integers $(a,b)$ satisfying $1 \leq a \leq b \leq N$, representing the endpoints of the segments $a \ldots b$ that need to be painted. For each candidate interval, if all fence segments within the interval are painted to the desired colors and all segments outside the interval are left unpainted, what is the minimum number of strokes needed? Note that Bessie does not actually paint anything during this process, so the answer for each candidate interval is independent.

The first line contains $N$ and $Q$. The next line contains an integer array of length $N$, representing the desired color of each fence segment. The following $Q$ lines each contain two space-separated integers $a$ and $b$, representing a candidate interval to be painted.

For each of the $Q$ candidate intervals, output one line containing the answer.

#### Sample 1 Explanation In this sample, painting the subarray with colors `1 1 2` requires $2$ strokes. Painting the subarray with colors `2 1 1 2` requires $3$ strokes. Painting the subarray with colors `1 2 2 1 1 2` requires $3$ strokes. Painting the subarray with colors `1 2 3 2` requires $3$ strokes. #### Subtask Properties - For $10\%$ of the testdata, $N,Q\le 100$. - For another $15\%$ of the testdata, $N,Q\le 5000$. - For another $25\%$ of the testdata, the input array does not contain numbers greater than $10$. - For the remaining $50\%$ of the testdata, there are no additional constraints. Problem by: Andi Qu, Brian Dean, Benjamin Qi. Translated by ChatGPT 5