题目描述

厌倦了辅助远程射手，Keria 现在正在创作一道关于支持区间查询的数据结构题。

对于一个长度为 m 的数组 $b = [b_1 ,b_2 \dots b_m]$，其中 $b_i = 0$ 或 $b_i = 1$，考虑以下的三元组移除操作：

1.选择三个索引 $1 \le i \lt j \lt k \le m$，使得这些位置上的元素相同（即 $b_i = b_j = b_k$）。

2.从数组中移除这三个元素。此操作的代价定义为 $min(k - j, j - i)$。移除后，数组的剩余部分会被拼接起来，并重新编号索引。

我们希望使用三元组移除操作将数组$b$清空。因此，我们定义一个数组的总代价为：为了将数组清空，所需执行的三元组移除操作的最小代价总和。如果无法将数组清空，则代价定义为 $-1$。

Keria 想要测试他的数据结构。为此，你需要回答 $q$ 个独立的查询。初始时，给定一个长度为 $n$ 的数组 $a = [a₁, a₂,\dots, a_n]$，其中 $a_i = 0$ 或 $a_i = 1$。对于每个查询，给定一个区间 $1 \le l \le r \le n$，你需要找出子数组 $[a_l, a_{l+1},\dots, a_r]$ 的代价。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t (1 \le t \le 10⁴)$。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ $(1 \le n, q \le 250000)$ —— 分别是数组的长度和查询的数量。 下一行包含 $n$ 个整数 $a_1, a_2, \dots, 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$ 之和不超过 250000。 保证所有测试用例的 $q$ 之和不超过 250000。

输出格式

对于每个测试用例，输出 $q$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 个查询的答案。

2
12 4
0 0 1 1 0 1 0 1 0 1 1 0
1 12
2 7
5 10
6 11
6 3
0 0 0 1 1 1
1 3
4 6
1 6

4
2
3
-1
1
1
2

样例解释

第一个测试用例的第一个查询（区间 $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$。