#include<bits/stdc++.h> // #define int long long #define endl '\n' #define lc(p) ((p)<<1) #define rc(p) ((p)<<1|1) using namespace std; const int N=2e5+7; int n,q; int S[N]; struct Node{ bool rev; int MaxL,MinL,Len,Sum,C1; Node(bool _r=0,int _M=0,int _m=0,int _l=0,int _Sum=0,int _C1=0){ rev=_r,MaxL=_M,MinL=_m,Len=_l,Sum=_Sum,C1=_C1; } }; Node operator+(Node a,Node b){ Node ret; ret.Len=a.Len+b.Len; ret.MaxL=max(max(a.MaxL,a.Sum+b.MaxL),0); ret.MinL=min(min(a.MinL,a.Sum+b.MinL),0); ret.Sum=a.Sum+b.Sum; ret.C1=a.C1+b.C1; return ret; } struct SGT{ Node d[N<<2]; inline void pu(int p){ d[p]=d[lc(p)]+d[rc(p)]; } inline void Calc(int p){ d[p].rev^=1; int M=-d[p].MinL,m=-d[p].MaxL; d[p].MaxL=M,d[p].MinL=m; d[p].Sum*=-1;d[p].C1=d[p].Len-d[p].C1; } inline void pd(int p){ if(!d[p].rev)return; Calc(lc(p)),Calc(rc(p)); d[p].rev=0; } inline void Build(int p,int l,int r){ d[p].Len=r-l+1;d[p].rev=0; if(l==r){ d[p].MaxL=max(2*S[l]-1,0); d[p].MinL=min(2*S[l]-1,0); d[p].Sum=2*S[l]-1; d[p].C1=S[l]; return; } int mid=l+r>>1; Build(lc(p),l,mid);Build(rc(p),mid+1,r); pu(p); } inline void Rv(int p,int l,int r,int L,int R){ if(L<=l&&r<=R)return void(Calc(p)); int mid=l+r>>1;pd(p); if(L<=mid)Rv(lc(p),l,mid,L,R); if(R>mid)Rv(rc(p),mid+1,r,L,R); pu(p); } inline int Qry(int p,int l,int r,int x){ if(l==r)return d[p].C1; int mid=l+r>>1;pd(p); // cout<<p<<" "<<l<<" "<<r<<" "<<d[p].C1<<endl; return (x<=mid?Qry(lc(p),l,mid,x):Qry(rc(p),mid+1,r,x)); } }T; signed main(){ #ifndef ONLINE_JUDGE freopen("medium.in","r",stdin); freopen("medium.out","w",stdout); #endif cin>>n; for(int i=1;i<=n;i++){ char t;cin>>t; S[i]=t-'A'; }S[0]=1; T.Build(1,0,n); cin>>q; while(q--){ int l,r;cin>>l>>r;l++,r++; T.Rv(1,0,n,l,r); Node x=T.d[1]; cout<<x.MaxL-x.C1+n+1<<endl;; }cout.flush(); return 0; }