先考虑 \([1,n]\) 的答案。
猜结论。将 \(a_i=0\) 视为 \(-1\)，做前缀和，每一次 \(<0\) 就意味着删掉一个 \(0\)。
再做一遍后缀和，执行同样的操作。
最后的答案就是区间长度 \(-\) 删掉的 \(0\) 的数量。
事实上，交一发，发现有 40pts，证明贪心是对的。
（但是我真的不会证贪心策略，我只能感性理解，如果有神仙知道请发到评论区 /kk）
那么考虑答案的变化过程。
比方说，当前前缀和数组 \(\text{pre}_i=-1\)，考虑对 \([i,n]\) 全体 \(+1\)。
继续碰到 \(\text{pre}'_j=-1\)（有原来 \(\text{pre}_j=-2\)），对 \([j,n]\) 全体 \(+1\)。
那么我们发现，统计做前缀和的过程，其实依次就是找到第一个 \(-1,-2,...,-x\)。
那么第一轮操作（统计前缀和）的操作次数，也就是 \(-\min\limits_{i=1}^n \{\text{pre}_i\}\)。
由于第一轮操作会对第二轮操作（统计后缀和）产生影响，考虑影响。
对于现在的后缀数组 \(\text{suf}'_i\)（在第一轮操作之前为 \(\text{suf}_i\)），\(\Delta=\) 在 \(i\) 右侧删除的 \(0\) 的个数。
想到这个不好维护，转化为差，即 \(-\min\limits_{i=1}^n\{\text{pre}_i\}-\) \(i\) 左侧删除的 \(0\) 的个数。
根据上侧的贪心策略，在 \(i\) 左侧删除的 \(0\) 的个数 \(=-\min\limits_{j=1}^{i-1}\{\text{pre}_j\}\)。
那么 \(\text{suf}'_i=\text{suf}_i+(-\min\limits_{i=1}^n\{\text{pre}_i\})-(-\min\limits_{j=1}^{i-1}\{\text{pre}_j\})\)。
则最终答案为 \(-\min\limits_{i=1}^n \{\text{pre}_i\}+(-\min\limits_{i=1}^n \{\text{suf}'_i\})=-\min\limits_{i=1}^n \{\text{suf}_i+\min\limits_{j=1}^{i-1}\{\text{pre}_j\}\}\)。
考虑怎么维护这个东西。
想想，答案其实是对于每一个段 \([i,n]\)，都求出 \(\min\limits_{j=1}^{i-1}\{\text{pre}_j\}\)。
枚举 \(i,j\) 的过程本质上也就是枚举互不相交的一个前缀和一个后缀。
问题就转化为，求互不相交的一个前缀和一个后缀的和的最小值。
继续转化，其实一个前缀和一个后缀的和的最小值，就等于全局和减去夹在中间的区间和。
问题等于 \(\max\limits_{1 \le l < r \le n}\{(\sum\limits_{k=1}^n a_k)-(\sum\limits_{k=l+1}^{r-1}a_k)\}\)。
那么就转化为最大子段和问题。这个东西显然可以推广到区间上。
由于题目问的是最多剩下多少个数，所以要用区间长度减掉维护的答案。
#include <bits/stdc++.h>
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
using namespace std;
const int N = 5e5 + 10; int n, q;
struct Node { int al, sum, pre, suf; } t[N << 2];
inline Node pushup(Node f, Node s) {
Node res; res.sum = f.sum + s.sum;
res.pre = max(f.pre, f.sum + s.pre), res.suf = max(s.suf, s.sum + f.suf);
res.al = max(max(f.al, s.al), f.suf + s.pre); return res;
}
inline void build(int rt, int l, int r) {
if (l == r) {
char op; cin >> op;
t[rt].al = t[rt].sum = t[rt].pre = t[rt].suf = (op == '0'? -1 : 1);
if (t[rt].al < 0) t[rt].al = 0; return ;
}
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
t[rt] = pushup(t[ls], t[rs]); return ;
}
inline Node query(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) return t[rt];
int mid = (l + r) >> 1; Node f, s; int tag = 0;
if (L <= mid) f = query(ls, l, mid, L, R), ++tag;
if (R > mid) s = query(rs, mid + 1, r, L, R), tag += 2;
if (tag == 1) return f; if (tag == 2) return s;
return pushup(f, s);
}
inline void solve() {
int l, r; cin >> l >> r;
Node res = query(1, 1, n, l, r); int len = res.al - res.sum;
if (len >= r - l + 1) cout << -1 << endl;
else cout << r - l + 1 - len << endl; return ;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> q; build(1, 1, n);
while (q--) solve(); return 0;
}