Problem Description

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?

Input Format

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]$.

Output Format

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.

8 4
3 3 3 2 2 3 4 7
1 3
3 6
1 7
5 8

1
0
1
4

6 3
2 1 1 2 2 1
1 6
1 4
3 6

2
0
0

Hint

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: