#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int tr[N<<2],lazy[N<<2],a[N];
struct Node {
	int l,r;
}q[N];
int midans,n,m;
void Push_Down(int p,int l,int r) {
	if (lazy[p]==-1||l==r)return;
	int mid = (l+r)>>1;
	tr[p<<1] = (mid-l+1)*lazy[p];
	tr[p<<1|1] = (r-mid)*lazy[p];
	lazy[p<<1] = lazy[p<<1|1] = lazy[p];
	lazy[p] = -1;
}
void Build(int p,int l,int r) {
	lazy[p] = -1;
	if (l==r) {
		tr[p] = a[l] > midans;
		return;
	}
	int mid = (l+r)>>1;
	Build(p<<1,l,mid);
	Build(p<<1|1,mid+1,r);
	tr[p] = tr[p<<1]+tr[p<<1|1];
}
void Update(int p,int l,int r,int a,int b,int c) {
	if (a > b) return;
	Push_Down(p,l,r);
	if (l >= a && r <= b) {
		tr[p] = (r-l+1)*c;
		lazy[p] = c;
		return;
	}
	int mid = (l+r)>>1;
	if (a <= mid) Update(p<<1,l,mid,a,b,c);
	if (b > mid) Update(p<<1|1,mid+1,r,a,b,c);
	tr[p] = tr[p<<1] + tr[p<<1|1];
}
int Getans(int p,int l,int r,int a,int b) {
	Push_Down(p,l,r);
	if (l >= a && r <= b) return tr[p];
	int ans = 0;
	int mid = (l+r)>>1;
	if (a <= mid) ans+= Getans(p<<1,l,mid,a,b);
	if (b > mid) ans+= Getans(p<<1|1,mid+1,r,a,b);
	return ans;
}
bool check(int x) {
	midans = x;
	Build(1,1,n);
	for (int i = 1;i<= m;i++) {
		int L = min(q[i].l,q[i].r);
		int R = max(q[i].l,q[i].r);
		int tmp = Getans(1,1,n,L,R);
		if (q[i].l < q[i].r) {
			Update(1,1,n,L,R-tmp,0);
			Update(1,1,n,R-tmp+1,R,1);
		} else {
			Update(1,1,n,L,L+tmp-1,1);
			Update(1,1,n,L+tmp,R,0);
		}
	}
	int midpos = (n>>1)+1;
	int t = Getans(1,1,n,midpos,midpos);
	return t == 1;
}
int GetFinalans() {
	int l = 1,r = n+1;
	while (l < r) {
		int mid = (l+r)>>1;
		if (check(mid))l = mid+1;
		else r = mid;
	}
	return l;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i = 1;i<= n;i++)scanf("%d",&a[i]);
	for (int i = 1;i<= m;i++)
		scanf("%d%d",&q[i].l,&q[i].r);
	printf("%d\n",GetFinalans());
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
char s[N];
int sum[N];
int lsum[N];
int k[N],id[N],ans[N],que[N],head,tail;
int main()
{
	int n,q;
	scanf("%s",s+1);
	n = strlen(s+1);
	scanf("%d",&q);
	for (int i = 1;i<= q;i++)
	{
		scanf("%d",&k[i]);
		id[i] = k[i];
	}
	sort(id+1,id+q+1);
	int cnt = 0;
	for (int i = 1;i<= q;i++)
		if (id[i]!=id[cnt])
			id[++cnt] = id[i];
	for (int i = 1;i<= n;i++)
	{
		sum[i] = sum[i-1]+(s[i]=='1');
		lsum[i] = 2*sum[i]-i;
	}
	for (int i = 1;i<= cnt;i++)
	{
		int K = id[i];
		head = tail = 1;
		que[1] = 0;
		ans[K] = ans[id[i-1]];
		for (int j = 1;j<= n;j++) {
			while (head <= tail && sum[j]-sum[que[head]] > K)head++;
			if (head<=tail)ans[K] = max(ans[K],lsum[que[head]]+j-2*sum[j]+K);
			while (head <= tail && lsum[j]>=lsum[que[tail]])tail--;
			que[++tail] = j;
		}
		ans[K] = min(ans[K],n-sum[n]);
	}
	for (int i = 1;i<= q;i++)
		printf("%d\n",ans[k[i]]);
	return 0;
}