P15850 [NOISG 2026 Finals] Gemstones

You are playing a puzzle game featuring $n$ gemstones in a row, numbered from $1$ to $n$ from left to right. The $i$-th gemstone has colour $c[i]$. At any point, you may select two adjacent gemstones of the same colour and delete them. Then, the gemstones on either side slide together to close the gap, possibly creating new adjacent pairs. You will be given $q$ independent scenarios. In the $j$-th scenario, you will only consider gemstones starting from gemstone $l[j]$ and ending at gemstone $r[j]$. Assuming you perform an optimal sequence of deletions, what is the minimum number of gemstones that can be left behind?

Your program must read from standard input. The first line of input contains two space-separated integers $n$ and $q$. The second line of input contains $n$ space-separated integers $c[1], c[2], \ldots, c[n]$. The next $q$ lines of input each contain two space-separated integers. The $i$-th of these lines contains $l[i]$ and $r[i]$.

Your program must print to standard output. The output should contain $q$ lines. The $i$-th of these lines should contain one integer, the answer to the $i$-th scenario.

### Sample Test Case 1 Explanation The $n = 8$ gemstones are shown in the diagram below. :::align{center}  ::: In the first scenario, only the first three gemstones should be considered. Deleting any two adjacent gemstones will leave exactly one behind, after which it is impossible to delete any more gemstones. Hence, the answer is $1$. In the second scenario, gemstones can be deleted in the following manner, leaving none behind: :::align{center}  ::: In the third scenario, gemstones can be deleted in the following manner, leaving one behind: :::align{center}  ::: In the fourth scenario, no gemstones can be deleted. Hence, the answer is $4$. ### Subtasks For all test cases, the input will satisfy the following bounds: - $1 \le n \le 10^6$ - $1 \le q \le 500\,000$ - $1 \le c[i] \le 10^9$ for all $1 \le i \le n$ - $1 \le l[j] \le r[j] \le n$ for all $1 \le j \le q$ Your program will be tested on input instances that satisfy the following restrictions: | Subtask | Score | Additional Constraints | |:-------:|:-----:|:----------------------:| | 0 | 0 | Sample test cases | | 1 | 2 | $c[1] = c[2] = \cdots = c[n]$ | | 2 | 5 | Gemstones of the same colour form a contiguous subarray (If $c[i] = c[j]$ and $i < j$, then $c[i] = c[i+1] = \cdots = c[j]$) | | 3 | 9 | $n, q \le 2000$ | | 4 | 4 | $l[j] = 1$ for all $1 \le j \le q$ | | 5 | 8 | There are exactly two gemstones of each colour | | 6 | 16 | $c[i] \le 2$ for all $1 \le i \le n$ | | 7 | 18 | $n, q \le 100\,000$ | | 8 | 15 | $n, q \le 300\,000$ | | 9 | 23 | No additional constraints |