P8304 [CoE R4 D] 01 String

Define a good $01$ string $\mathcal{S}$ that satisfies the following conditions: + $\mathcal{S}$ is non-empty. + For any prefix $\mathcal {S} [1\dots p] (p \in [1,|\mathcal S|])$, the number of $0$ is not greater than the number of $1$. + For any suffix $\mathcal S[p\dots |\mathcal{S}|] (p \in [1,|\mathcal S|])$, the number of $0$ is not greater than the number of $1$. Now you are given a $01$ string $\mathcal{T}$ of length $n$. There are $q$ queries. In each query, you are given a pair $l, r$. Find the length of the longest good $01$ **subsequence** in $\mathcal{T}[l\dots r]$. If there is no good $01$ subsequence, output $-1$. Note: A **subsequence** is a new sequence formed by removing some elements without changing the relative order of the remaining elements.

The first line contains two integers $n, q$, representing the length of the $01$ string and the number of queries. The second line contains a $01$ string of length $n$, representing $\mathcal{T}$. The next $q$ lines each contain two integers $l, r$, representing one query.

Output $q$ lines. Each line contains one integer, representing the answer to each query in order.

### Sample Explanation In the first query, the queried string is $0$. No subsequence is good, so the answer is $-1$. In the second query, the queried string is $01001$. The subsequence $101$ is good and is the longest, so the answer is $3$. In the third query, the queried string is $10010101$. The subsequence $1010101$ is good and is the longest, so the answer is $7$. In the fourth query, the queried string is $0100101011$. The subsequence $10101011$ is good and is the longest, so the answer is $8$. --- ### Constraints **This problem uses bundled testdata.** | Subtask | Score | $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$ | For $100\%$ of the testdata, $1 \leq l \leq r \leq n \leq 5 \times 10^5$, and $1 \leq q \leq 5 \times 10^5$. Translated by ChatGPT 5