题目描述

你正在玩一个益智游戏，游戏中有 $n$ 颗宝石排成一行，从左到右编号为 $1$ 到 $n$。第 $i$ 颗宝石的颜色为 $c[i]$。

在任何时刻，你可以选择两颗相邻且颜色相同的宝石并将它们删除。然后，两侧的宝石会滑动以填补空隙，这可能会创造出新的相邻宝石对。

你将面对 $q$ 个独立的场景。在第 $j$ 个场景中，你只考虑从宝石 $l[j]$ 开始到宝石 $r[j]$ 结束的这一段宝石。假设你执行了最优的删除序列，最终最少可能剩下多少颗宝石？

输入格式

你的程序需要从标准输入读取数据。

输入的第一行包含两个由空格分隔的整数 $n$ 和 $q$。

输入的第二行包含 $n$ 个由空格分隔的整数 $c[1], c[2], \ldots, c[n]$。

接下来的 $q$ 行输入，每行包含两个由空格分隔的整数。其中第 $i$ 行包含 $l[i]$ 和 $r[i]$。

输出格式

你的程序需要向标准输出写入数据。

输出应包含 $q$ 行。其中第 $i$ 行应包含一个整数，即第 $i$ 个场景的答案。

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

提示

样例测试 #1 解释

$n = 8$ 颗宝石如下图所示。

:::align{center} :::

在第一个场景中，只考虑前三个宝石。删除任意两个相邻的宝石后，会恰好剩下一颗宝石，之后无法再进行任何删除。因此，答案是 $1$。

在第二个场景中，可以按以下方式删除宝石，最终一颗不剩：

:::align{center} :::

在第三个场景中，可以按以下方式删除宝石，最终剩下一颗：

:::align{center} :::

在第四个场景中，无法删除任何宝石。因此，答案是 $4$。

子任务

对于所有测试用例，输入数据满足以下限制：

• $1 \le n \le 10^6$
• $1 \le q \le 500\,000$
• 对于所有 $1 \le i \le n$，有 $1 \le c[i] \le 10^9$
• 对于所有 $1 \le j \le q$，有 $1 \le l[j] \le r[j] \le n$

你的程序将在满足以下限制的输入实例上进行测试：

翻译由 DeepSeek V3.2 完成