题目描述

可爱猪猪 厌倦了为远程输出型英雄提供支援，现在她设计了一个关于支持区间查询的数据结构问题。

对于一个长度为 $m$ 的数组 $b = [b_1, b_2, \ldots, b_m]$，其中 $b_i=0$ 或 $b_i=1$，定义如下的“三元组移除”操作：

1. 选择三个下标 $1 \le i < j < k \le m$，使得这三个位置上的元素相同（即 $b_i = b_j = b_k$）。
2. 将这三个元素从数组中移除。该操作的代价为 $\min(k-j, j-i)$。移除后，剩余的数组连接起来，重新编号。

我们的目标是通过三元组移除操作，将数组 $b$ 变为空。数组的总代价定义为：将数组清空所需一系列三元组移除操作代价之和的最小值。如果无法将数组清空，则代价定义为 $-1$。

可爱猪猪 希望测试她的数据结构。为此，你需要回答 $q$ 个相互独立的查询。最初你会得到一个长度为 $n$ 的数组 $a = [a_1, a_2, \ldots, a_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$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 次查询的区间。

保证所有测试数据中 $n$ 之和不超过 $250\,000$，$q$ 之和不超过 $250\,000$。

输出格式

对于每组测试数据，输出 $q$ 行，每行一个整数，为第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

4
2
3
-1
1
1
2

说明/提示

第一组样例，第一条查询（1 12）的解释：

子数组为 $[0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0]$。其中有六个 $0$ 和六个 $1$。一种可能的最优移除方案如下：

1. 移除下标 $3$、$4$、$6$ 的三个 $1$。代价为 $\min(6-4, 4-3) = \min(2, 1) = 1$。移除后数组为 $[0, 0, 0, 0, 1, 0, 1, 1, 0]$。
2. 移除下标 $1$、$2$、$3$ 的三个 $0$。代价为 $\min(3-2, 2-1) = \min(1, 1) = 1$。移除后数组为 $[0, 1, 0, 1, 1, 0]$。
3. 移除下标 $2$、$4$、$5$ 的三个 $1$。代价为 $\min(5-4, 4-2) = \min(1, 2) = 1$。移除后数组为 $[0, 0, 0]$。
4. 移除下标 $1$、$2$、$3$ 的三个 $0$。代价为 $\min(3-2, 2-1) = \min(1, 1) = 1$。此时数组变为空。

总代价为 $1+1+1+1=4$。