厌倦了支持范围进位,Keria 现在正在创建一个关于支持范围查询的数据结构问题。
对于长度为 $$$m$$$ 的数组 $$$b = [b_1, b_2, \ldots, b_m]$$$,其中 $$$b_i=0$$$ 或 $$$b_i=1$$$,请考虑以下内容 三重删除 操作:
- 选择三个索引 $$$1 \le i \lt j \lt k \le m$$$ 使得这些位置的元素相同 ($$$b_i = b_j = b_k$$$)。
- 从数组中删除这三个元素。该操作的成本定义为$$$\min(k-j, j-i)$$$。删除后,数组的剩余部分将被连接起来,并重新标记它们的索引。
我们希望使用以下命令将数组 $$$b$$$ 清空 三重删除 操作。因此,我们定义 总成本 数组的 作为以下成本的最小可能总和 将数组清空所需的 三重删除 操作。如果不可能使数组为空,则成本定义为$$$-1$$$。
Keria 想测试他的数据结构。为此,您必须回答 $$$q$$$ 独立查询。最初,给定一个数组 $$$a = [a_1, a_2, \ldots, a_n]$$$,长度为 $$$n$$$,其中 $$$a_i=0$$$ 或 $$$a_i=1$$$。对于每个查询,您都会获得一个范围 $$$1 \le l \le r \le n$$$,并且必须找到数组 $$$[a_l, a_{l+1}, \ldots, a_r]$$$ 的成本。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 250\,000$$$) - 数组的长度和查询的数量。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$($$$a_i = 0$$$ 或 $$$a_i=1$$$)— 数组的元素。
然后是 $$$q$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) - 第 $$$i$$$ 查询的子数组范围。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$250\,000$$$。
保证所有测试用例的 $$$q$$$ 总和不超过 $$$250\,000$$$。
输出
对于每个测试用例,输出 $$$q$$$ 行。第 $$$i$$$ 行应包含一个整数,表示第 $$$i$$$ 查询的答案。
示例
输入复制
212 40 0 1 1 0 1 0 1 0 1 1 01 122 75 106 116 30 0 0 1 1 11 34 61 6
输出复制
423-1112
注意
第一个测试用例的解释,第一个查询(1 12):
子数组为 $$$[0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0]$$$。有六个 $$$0$$$ 和六个 $$$1$$$。可能的最佳操作顺序是:
- 删除索引 $$$3$$$、$$$4$$$、$$$6$$$ 处的三个 $$$1$$$。成本为 $$$\min(6-4, 4-3) = \min(2, 1) = 1$$$。该数组变为 $$$[0, 0, 0, 0, 1, 0, 1, 1, 0]$$$。
- 删除索引 $$$1$$$、$$$2$$$、$$$3$$$ 处的三个 $$$0$$$。成本为 $$$\min(3-2, 2-1) = \min(1, 1) = 1$$$。该数组变为 $$$[0, 1, 0, 1, 1, 0]$$$。
- 删除索引 $$$2$$$、$$$4$$$、$$$5$$$ 处的三个 $$$1$$$。成本为 $$$\min(5-4, 4-2) = \min(1, 2) = 1$$$。该数组变为 $$$[0, 0, 0]$$$。
- 删除索引 $$$1$$$、$$$2$$$、$$$3$$$ 处的三个 $$$0$$$。成本为 $$$\min(3-2, 2-1) = \min(1, 1) = 1$$$。数组现在是空的。
总成本为$$$1+1+1+1=4$$$。