你正在玩一个益智游戏，游戏中有 $n$ 颗排成一行的宝石，从左到右编号为 $1$ 到 $n$。第 $i$ 颗宝石的颜色为 $c[i]$。
在任何时候，你可以选择两颗颜色相同的相邻宝石并将它们删除。随后，这两颗宝石两侧的宝石会向中间靠拢以填补空隙，这可能会产生新的相邻对。
你将收到 $q$ 个独立的场景。在第 $j$ 个场景中，你仅考虑从第 $l[j]$ 颗宝石到第 $r[j]$ 颗宝石之间的宝石。假设你执行最优的删除序列，剩下的宝石数量最少是多少？
输入格式
你的程序必须从标准输入读取数据。
第一行包含两个空格分隔的整数 $n$ 和 $q$。
第二行包含 $n$ 个空格分隔的整数 $c[1], c[2], \dots, c[n]$。
接下来的 $q$ 行，每行包含两个空格分隔的整数。第 $i$ 行包含 $l[i]$ 和 $r[i]$。
输出格式
你的程序必须打印到标准输出。
输出应包含 $q$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个场景的答案。
数据范围
对于所有测试用例，输入满足以下限制：
- $1 \le n \le 10^6$
- $1 \le q \le 500\,000$
- $1 \le c[i] \le 10^9$，对于所有 $1 \le i \le n$
- $1 \le l[j] \le r[j] \le n$，对于所有 $1 \le j \le q$
你的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 0 | 0 | 样例测试用例 |
| 1 | 2 | $c[1] = c[2] = \dots = c[n]$ |
| 2 | 5 | 同色宝石形成连续子数组（若 $c[i] = c[j]$ 且 $i < j$，则 $c[i] = c[i + 1] = \dots = c[j]$） |
| 3 | 9 | $n, q \le 2000$ |
| 4 | 4 | $l[j] = 1$，对于所有 $1 \le j \le q$ |
| 5 | 8 | 每种颜色恰好有两颗宝石 |
| 6 | 16 | $c[i] \le 2$，对于所有 $1 \le i \le n$ |
| 7 | 18 | $n, q \le 100\,000$ |
| 8 | 15 | $n, q \le 300\,000$ |
| 9 | 23 | 无附加限制 |
样例
输入格式 1
8 4 3 3 3 2 2 3 4 7 1 3 3 6 1 7 5 8
输出格式 1
1 0 1 4
说明
样例 1 的解释： $n = 8$ 颗宝石如下图所示。
在第一个场景中，仅考虑前三颗宝石。删除任意两颗相邻的同色宝石会留下一颗，之后无法再进行删除。因此，答案为 $1$。
在第二个场景中，宝石可以按以下方式删除，不留任何宝石：
在第三个场景中，宝石可以按以下方式删除，留下一颗宝石：
在第四个场景中，无法删除任何宝石。因此，答案为 $4$。