Longest Good 01 Subsequence

A binary string \(\mathcal{S}\) is called good if it satisfies the following conditions:

1. \(\mathcal{S}\) is non-empty.
2. For every prefix \(\mathcal{S}[1 \dots p]\) \((1 \leq p \leq |\mathcal{S}|)\), the number of 0's is not greater than the number of 1's.
3. For every suffix \(\mathcal{S}[p \dots |\mathcal{S}|]\) \((1 \leq p \leq |\mathcal{S}|)\), the number of 0's is not greater than the number of 1's.

You are given a binary string \(\mathcal{T}\) of length \(n\) and \(q\) queries. Each query is represented by two integers \(l\) and \(r\). For each query, consider the substring \(\mathcal{T}[l \dots r]\) and determine the length of the longest good 01 subsequence (a sequence obtained by deleting some characters without changing the order) of it. If no good subsequence exists, output \(-1\).

Note: A good string, if constructed in the following form, is valid: choose an integer \(d\) (with \(d \ge 1\)) and an integer \(k\ge 0\), then form the string as:

[ \underbrace{1,1,\dots,1}_{d\text{ times}} \ followed \ by \ k \text{ pairs of } (0,1), ]

Such a string has \(a = d+k\) ones and \(b = k\) zeros, with a final difference \(a-b = d\). It can be verified that every prefix and every suffix of such a sequence will have at most \(d\) more 1's than 0's.

Given the counts of 1's and 0's in \(\mathcal{T}[l \dots r]\) as \(A\) and \(Z\) respectively, the optimal strategy is as follows:

• If \(A = 0\), output \(-1\) because any good sequence must start with 1.
• If \(Z \ge A-1\), one can form a sequence of length \(2A-1\) (by taking one 1 to be the initial block and pairing the remaining \(A-1\) ones with zeros).
• If \(Z < A-1\), then the maximum achievable length is \(A + Z\) (using all available 0's and 1's in a valid paired manner).

Your task is to answer each query accordingly.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\) --- the length of the string and the number of queries.

The second line contains a binary string \(\mathcal{T}\) of length \(n\) consisting of characters '0' and '1'.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) \((1 \le l \le r \le n)\) representing a query.

outputFormat

For each query, output a single integer denoting the length of the longest good 01 subsequence in \(\mathcal{T}[l \dots r]\). If no good subsequence exists, output \(-1\).

sample

5 3
11010
1 5
2 4
3 3

5
3
-1

</p>