[R63F]这是一个01串题3 - 代码源竞赛平台

时空限制

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]$ ， $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$ 。

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

子任务编号	分数	$n\le$
$1$	$30$	$100$
$2$	$30$	$2000$
$3$	$40$	$2\times 10^5$

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