#include<bits/stdc++.h> using namespace std; const int N=2e5+10; string str; int n,q; const int inf=1e9; struct Mat{ int a00,a01,a10,a11; }; Mat operator*(Mat a,Mat b){ Mat c; c.a00=max(max(a.a00+b.a00,a.a01+b.a10),-inf); c.a01=max(max(a.a00+b.a01,a.a01+b.a11),-inf); c.a10=max(max(a.a10+b.a00,a.a11+b.a10),-inf); c.a11=max(max(a.a10+b.a01,a.a11+b.a11),-inf); return c; } Mat A=(Mat){-1,-inf,0,0},B=(Mat){1,-inf,-inf,0},st=(Mat){0,-1,-inf,-inf}; struct segtree{ #define ls p*2 #define rs p*2+1 #define mid (l+r)/2 int T[N<<2][2];Mat M[N<<2][2]; int tg[N<<2]; void pu(int p){ T[p][0]=T[ls][0]+T[rs][0]; T[p][1]=T[ls][1]+T[rs][1]; M[p][0]=M[rs][0]*M[ls][0]; M[p][1]=M[rs][1]*M[ls][1]; } void pd(int p){ if(!tg[p]) return ; tg[p]=0;tg[ls]^=1;tg[rs]^=1; swap(T[ls][0],T[ls][1]); swap(M[ls][0],M[ls][1]); swap(T[rs][0],T[rs][1]); swap(M[rs][0],M[rs][1]); } void bd(int p,int l,int r){ if(l==r){ if(str[l]=='A'){ M[p][0]=A;M[p][1]=B; T[p][0]=0;T[p][1]=1; }else{ M[p][0]=B;M[p][1]=A; T[p][0]=1;T[p][1]=0; }return ; }bd(ls,l,mid);bd(rs,mid+1,r);pu(p); } void upd(int p,int l,int r,int pl,int pr){ if(pl<=l&&r<=pr){ tg[p]^=1; swap(T[p][0],T[p][1]); swap(M[p][0],M[p][1]); return ; }pd(p); if(pl<=mid) upd(ls,l,mid,pl,pr); if(pr>mid) upd(rs,mid+1,r,pl,pr); pu(p); } }sgt; int main(){ //freopen("medium.in","r",stdin); //freopen("medium.out","w",stdout); cin>>n>>str>>q; str=" B"+str+"A "; n+=2;sgt.bd(1,1,n); for(int i=1;i<=q;i++){ int l,r;cin>>l>>r; l+=2;r+=2;sgt.upd(1,1,n,l,r); int ans=(st*sgt.M[1][0]).a00+n-sgt.T[1][0]; cout<<ans<<'\n'; } return 0; }