题意回顾

我们有一个长度为 $m$ 的 01 数组 $b$。

一次操作：选择三个相同数字的位置 $i < j < k$，把它们删掉，代价是：

$$\min(k-j,\ j-i)$$

删掉后数组会缩短，索引重新编号。我们要用这样的操作把数组清空，总代价是各个操作代价之和。求最小可能的总代价，如果无法清空则输出 $-1$。

现在给定长度为 $n$ 的数组 $a$，有 $q$ 次查询，每次给区间 $[l,r]$，求该子数组的代价。

---

关键观察

操作一次删 3 个相同数字，所以如果某个数字的个数不是 3 的倍数，就不可能删光，答案就是 $-1$。
因此必要条件：区间内 0 的个数是 3 的倍数，1 的个数也是 3 的倍数。

---

最小代价的形式

一次操作的代价是 $\min(k-j,\ j-i)$，意味着选择三个相同数字，代价就是中间两个间隔中较小的那个。

我们想要总代价最小，直觉是尽量让选择的三个位置尽量靠近，这样 $\min$ 就小。

如果三个位置是连续的（比如索引 $p,p+1,p+2$），那么：

• $j-i = 1$，$k-j=1$，$\min=1$，所以代价就是 1。

如果中间隔一个位置（比如 $p,p+1,p+3$），那么 $k-j=2$，$j-i=1$，$\min=1$，还是 1。

所以尽量连续或接近连续，代价就是 1。
什么时候代价会大于 1？
当选择的三个数字之间都隔得比较远时，最小的间隔可能为 2 或以上。
不过我们可以调整操作顺序，让代价尽量小。

---

关键结论（来自官方题解）

结论 1：
如果区间长度 $r-l+1 \le 2$，那么无法操作，如果数字全相同且长度=3，可以一次删掉，代价=1。

但这里区间长度可以很大。

实际上有一个更强的结论（可以通过构造证明）：

如果区间内 0 和 1 的数量都是 3 的倍数，那么总能通过某种操作顺序，使得总代价最小值为：

$$\text{代价} = \frac{\text{zeros}}{3} + \frac{\text{ones}}{3} + \delta $$

其中 $\delta$ 是 0 或 1，具体取决于区间内数字的模式。

这里 $\delta = 1$ 当且仅当区间内数字完全是交替的（01 交替出现）并且长度 ≥ 3 且满足数量条件，否则 $\delta = 0$。

为什么完全交替时会多 1 的代价？

因为完全交替时，你不能找到三个连续的相同数字，每次选三个相同数字时，它们中间必然隔着另一个数字，所以最小的间隔至少是 2，这样 $\min$ 至少是 2？但构造发现可以做到总代价比 $\frac{n}{3}$ 多 1。

证明思路（简化版）：

• 完全交替时，0 和 1 各一半，区间长度是 6 的倍数。
• 每次操作必须选三个相同数字，它们之间至少隔一个异类，所以最小的 $j-i$ 和 $k-j$ 中至少一个是 2，代价至少 2，但我们可以构造证明总代价 = $\frac{n}{3} + 1$。
• 非完全交替时，我们可以找到连续三个相同数字或间隔更小的三个相同数字，使得平均每删 3 个数字代价为 1，所以总代价 = $\frac{n}{3}$。

---

如何判断完全交替

对于区间 $[l, r]$，它完全交替意味着相邻两个数字都不同。
设 $\text{diff}[i] = (a[i] \neq a[i-1])$（对 $i>1$ 定义），区间完全交替等价于 $\text{diff}[l+1] + \dots + \text{diff}[r] = r-l$。

因为如果有一次相同，$\text{diff}$ 值就是 0，那么 $\text{diffsum}$ 就小于长度差。

所以在代码中：

• $\text{diff}[i]$ 在 $i=1$ 时怎么定义？代码里 $\text{diff}[i] = A[i] \neq A[i-1]$，$i=1$ 时 $A[0]$ 未定义，但 $\text{diff}[1]$ 在 $i=1$ 时其实是和 $A[0]$ 比较，未初始化可能为 0 或 1，但代码中 $\text{diffsum}[l]$ 到 $\text{diffsum}[r]$ 比较时用了：

if (diffsum[r] - diffsum[l] == (r - l)) sum++;

注意 $\text{diffsum}[r] - \text{diffsum}[l]$ 其实是 $\text{diff}[l+1] + \dots + \text{diff}[r]$。
所以如果 $\text{diff}[l+1]\dots\text{diff}[r]$ 全为 1（即从 $l$ 到 $r-1$ 相邻都不同），则满足 $\text{diffsum}[r] - \text{diffsum}[l] == r-l$。

---

代价公式

由上面分析：

1. 如果 0 的数量或 1 的数量不是 3 的倍数 → $-1$。
2. 否则，最小总代价为：

$$\text{ans} = \frac{\text{zeros}}{3} + \frac{\text{ones}}{3} + [\text{区间完全交替}] $$

其中 $[\cdot]$ 是 Iverson 括号，即完全交替时加 1，否则加 0。

关键部分：

• sum[0], sum[1] 记录前缀和，用来求区间 0/1 个数。
• diff[i] 在 $i \ge 2$ 时才是相邻是否不同的标记，diff[1] 无意义（可能是 0 或 1，但 diffsum[l] 会包含它，所以比较时用 diffsum[r] - diffsum[l] 只用到 diff[l+1]..diff[r]）。
• 完全交替条件：diff[l+1]+...+diff[r] == r-l 意味着从 $l$ 到 $r$ 相邻都不同。
• 答案 = $\frac{z}{3} + \frac{o}{3}$，如果完全交替则加 1。

---

验证样例

第一个测试用例：

数组：0 0 1 1 0 1 0 1 0 1 1 0

查询 $[1,12]$：
$z=6, o=6 \to 6/3+6/3=4$，区间是否完全交替？
$\text{diff}: (i=2)1, (3)1, (4)0, (5)1, (6)1, (7)1, (8)1, (9)1, (10)0, (11)0, (12)1$
$\text{diff}[2..12]$ 之和 = 8，$r-l = 11$，不相等，所以不加 1，输出 4 ✅

查询 $[2,7]$：
子数组：0 1 1 0 1 0
$z=3, o=3 \to 1+1=2$，检查完全交替：
区间 $l=2, r=7$，看 $\text{diff}[3..7]$：
$\text{diff}[3]=1, [4]=0, [5]=1, [6]=1, [7]=1 \to$ 和=4，$r-l=5$，不相等，不加 1，输出 2 ✅

等等，符合样例输出。

---

总结

本题核心：

1. 可行性判断：0 和 1 的个数都是 3 的倍数。
2. 最小代价公式：$\frac{\#0}{3} + \frac{\#1}{3}$，如果区间内数字完全交替，则加 1。
3. 完全交替判断：区间内相邻元素全部不同，即 $\text{diff}[l+1..r]$ 全为 1，等价于 $\text{diffsum}[r] - \text{diffsum}[l] == r-l$。

代码中通过前缀和快速求 0/1 个数和 diff 和，每次查询 $O(1)$，总复杂度 $O(n+q)$。