时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的 $01$ 串 $s$。

定义一个字符串是“错列串”，当且仅当任意两个相邻字符都不同。例如 10101、0101 是错列串，而 110、00 不是。

一次操作可以选择字符串中相邻的两个字符并交换它们。

定义 $h(T)$ 为：将字符串 $T$ 变成错列串所需的最少操作次数。若无论如何交换都无法变成错列串，则 $h(T) = -1$。

现在给出 $Q$ 个询问，每次给定区间 $[l, r]$，求 $h(s[l, r])$。

格式

输入格式

第一行包含两个正整数 $n$ 和 $Q$，分别表示字符串的长度和询问的个数。

第二行包含一个长度为 $n$ 的 $01$ 串 $s$。

接下来 $Q$ 行，每行包含两个正整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示询问的区间。

输出格式

输出共 $Q$ 行，每行包含一个整数，表示对应询问的答案。

样例

样例输入 #1

5 4
01100
1 5
2 3
1 4
3 5

样例输出 #1

1
-1
1
1

样例解释 #1

• 对于第一个询问 $[1, 5]$，$s[1, 5] =$ 01100。它的字符构成为 $3$ 个 0 和 $2$ 个 1。我们可以交换第 $3$ 个和第 $4$ 个字符，得到错列串 01010，只需 $1$ 次操作，因此答案为 $1$。
• 对于第二个询问 $[2, 3]$，$s[2, 3] =$ 11。无论如何交换也无法变成错列串，因此答案为 $-1$。
• 对于第三个询问 $[1, 4]$，$s[1, 4] =$ 0110。可以交换第 $1$ 个和第 $2$ 个字符（得到 1010），或交换第 $3$ 个和第 $4$ 个字符（得到 0101），最少操作次数为 $1$。
• 对于第四个询问 $[3, 5]$，$s[3, 5] =$ 100。可以交换第 $1$ 个和第 $2$ 个字符，得到 010，最少操作次数为 $1$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n, Q \le 2 \times 10^5$，$s$ 中仅包含字符 0 和 1，$1 \le l \le r \le n$。