[CoE R4 D] 01 串

定义一个好的 $01$ 串 $\mathcal{S}$ 满足以下条件： + $\mathcal{S}$ 非空。 + $\mathcal{S}$ 的任意一个前缀 $\mathcal {S} [1\dots p](p\in [1,|\mathcal S|])$ 中，$0$ 的数量都不多于 $1$ 的数量。 + $\mathcal{S}$ 的任意一个后缀 $\mathcal S[p\dots |\mathcal{S}|](p\in [1,|\mathcal S|])$ 中，$0$ 的数量都不多于 $1$ 的数量。 现在你得到了一个长度为 $n$ 的 $01$ 串 $\mathcal{T}$，有 $q$ 次询问，每次询问给定一对 $l,r$，求 $\mathcal{T}[l\dots r]$ 中的最长的好的 $01$ **子序列** 的长度。若没有好的 $01$ 子序列，则输出 $-1$。 注意：**子序列** 是指去除某些元素但不破坏余下元素的相对位置而形成的新序列。 ## Input 第一行两个整数 $n,q$，分别表示 $01$ 串的长度和询问次数。 第二行一个长度为 $n$ 的 $01$ 串，表示 $\mathcal{T}$。 接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。 ## Output 输出 $q$ 行，每行一个整数，依次表示每次询问的答案。 [samples] ## Note ### 样例解释 第一次询问中，询问的串为 $0$，没有任何的子序列是好的，所以答案是 $-1$。 第二次询问中，询问的串为 $01001$，子序列 $101$ 是好的且是最长的，所以答案是 $3$。 第三次询问中，询问的串为 $10010101$，子序列 $1010101$ 是好的且是最长的，所以答案是 $7$。 第四次询问中，询问的串为 $0100101011$，子序列 $10101011$ 是好的且是最长的，所以答案是 $8$。 --- ### 数据规模 **本题采用捆绑测试。** | 子任务 | 分值 | $n \le$ | $q \le$ | | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | $10$ | | $2$ | $20$ | $2000$ | $2000$ | | $3$ | $30$ | $8\times 10^4$ | $8\times 10^4$ | | $4$ | $10$ | $10^5$ | $1$ | | $5$ | $30$ | $5\times 10^5$ | $5\times 10^5$ | 对于 $100\%$ 的数据，$1 \leq l \leq r \leq n \leq 5 \times 10^5$，$1 \leq q \leq 5 \times 10^5$。