You are playing a puzzle game featuring gemstones in a row, numbered from to from left to right. The -th gemstone has colour .
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 independent scenarios. In the -th scenario, you will only consider gemstones starting from gemstone and ending at gemstone . 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 and .
The second line of input contains space-separated integers .
The next lines of input each contain two space-separated integers. The -th of these lines contains and .
输出格式
Your program must print to standard output.
The output should contain lines. The -th of these lines should contain one integer, the answer to the -th scenario.
样例
样例输入 1
8 4
3 3 3 2 2 3 4 7
1 3
3 6
1 7
5 8
样例输出 1
1
0
1
4
样例输入 2
6 3
2 1 1 2 2 1
1 6
1 4
3 6
样例输出 2
2
0
0
数据范围与提示
Sample Test Case 1 Explanation
The 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 .
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 .
Subtasks
For all test cases, the input will satisfy the following bounds:
for all
for all
Your program will be tested on input instances that satisfy the following restrictions:
Subtask
Score
Additional Constraints
0
Sample test cases
1
2
2
5
Gemstones of the same colour form a contiguous subarray (If and , then )
:::
:::
:::