题目背景

小李在海拉鲁进行冒险的时候遭遇了怪物袭击！
小李需要面对一排波克布林和莫力布林，但是手上拿着兽神弓，背包里一堆人马角的小李独自一人把这群怪物包围了。

题目描述

在小李面前有 莫力布林 和 波克布林 两种怪物，一共 $n$ 只。这些怪物站成一排，我们用 $0$ 代表波克布林，用 $1$ 代表莫力布林，这样这群怪物可以视作一个长度为 $n$ 的数组 $a=[a_1, a_2, \ldots, a_n]$，其中 $a_i \in [0, 1]$。

小李的兽神弓一次射击可以射出 $3$ 支箭矢，可以用于攻击多个目标。

同时，小李是一个强迫症患者，他的每次攻击 都只会射杀三只同一种类的怪物，并且消耗数值跟距离最近的两只怪物之间的距离相同的体力。

更正式地说，选择三个索引 $1 \leq i < j < k \leq m$，使得这些位置上的怪物相同，即 $a_i = a_j = a_k$，从怪群中击杀这三只怪物。这一攻击的体力消耗定义为 $\min(k−j, j−i)$。击杀怪物后，怪群的剩余部分将拼接在一起，并重新标注其索引。

小李想知道他击杀某个区间内的怪物 最少 需要消耗多少体力，为此，你必须回答 $q$ 个独立查询。

最初，他会给你一个长度为 $n$ 的整型数组 $a=[a_1,a_2,...,a_n]$，其中 $a_i \in [0,1]$。对于每个查询，你都会得到一个范围 $l, r$ $(1 \leq l \leq r \leq n)$ ，并必须找出击杀区间内怪物 $[a_l,a_{l+1},…,a_r]$ 的代价。

如果无法满足小李的强迫症，请输出 $-1$（即无法按照小李的方式恰好击杀区间内所有怪物、或有箭矢被浪费）。

输入格式

第一行包含两个整数 $n, q$ $(1 \leq n,q \leq 2.5 \times 10^{5})$，代表数组的长度和查询次数。

第二行包含 $n$ 个由空格分隔的整数 $a_1, a_2, \ldots, a_n$ $(a_i \in [0, 1])$，代表数组的元素。

接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ $(1 \leq l_i \leq r_i \leq n)$，代表第 $i$ 次查询的子数组范围。

输出格式

输出 $q$ 行，第 $i$ 行一个整数，代表第 $i$ 次查询的答案。

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

4
2
3
-1

说明

对于第一次查询 $l = 1, r = 12$，子数组为 $[0,0,1,1,0,1,0,1,0,1,1,0]$。有六只 波克布林 和 六只莫力布林。可能的最佳操作顺序是：

1. 击杀位于索引 $3, 4, 6$ 的三只 莫力布林。消耗 $\min(6−4,4−3)=\min(2,1)=1$。数组变为$[0,0,0,0,1,0,1,1,0]$；
2. 击杀位于索引 $1, 2, 3$ 的三只 波克布林。消耗 $\min(3−2,2−1)=\min(1,1)=1$。数组变为 $[0,1,0,1,1,0]$；
3. 击杀位于索引 $2, 4, 5$ 的三只 莫力布林。消耗 $\min(5−4,4−2)=\min(1,2)=1$。数组变为 $[0,0,0]$；
4. 击杀位于索引 $1, 2, 3$ 的三只 波克布林。消耗 $\min(3−2,2−1)=\min(1,1)=1$。现在数组为空。

总消耗为 $1+1+1+1=4$。