三元组移除

题目描述

Y 同学定义了一种在 01 序列上的“三元组移除”操作。

给定一个长度为 $m$ 的 01 序列 $B = \{b_1, b_2, \dots, b_m\}$，一次操作流程如下：

1. 选择三个下标 $i, j, k$，满足 $1 \le i < j < k \le m$ 且 $b_i = b_j = b_k$。
2. 将这三个元素从序列中移除，其余元素拼接起来形成新序列。
3. 这次操作产生 $\min(k-j, j-i)$ 的代价。

一个 01 序列的总代价，被定义为通过一系列“三元组移除”操作将其变为空序列，所需支付的最小代价之和。如果一个序列无论如何都无法被清空，则其总代价为 $-1$。

现在，你得到了一个长度为 $N$ 的初始 01 序列 $A$。你需要回答 $Q$ 次独立的查询。每次查询给定一个区间 $[l, r]$，你需要计算子序列 $A[l..r]$ 的总代价。

输入格式

第一行输入一个整数 $T_{case}$，表示测试数据的组数。

对于每组测试数据： 第一行包含两个整数 $N$ 和 $Q$。 第二行包含 $N$ 个整数（$0$ 或 $1$），表示序列 $A$。 接下来的 $Q$ 行，每行包含两个整数 $l_i, r_i$，描述一次查询。

输出格式

对于每次查询，输出一行一个整数，表示对应子序列的总代价。

样例

样例输入 #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

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T_{case} \le 10^4$
• $1 \le N, Q \le 250,000$
• $a_i \in \{0, 1\}$
• $1 \le l_i \le r_i \le N$
• 所有测试用例的 $N$ 之和不超过 $250,000$。
• 所有测试用例的 $Q$ 之和不超过 $250,000$。