#include<bits/stdc++.h> using namespace std; #define LD long double #define pii pair<int,int> #define fr first #define sc second #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} const int MAXN=200010; int n,q,a[MAXN],p[MAXN],k; char s[MAXN]; struct segtree{ #define lson (pos<<1) #define rson (pos<<1|1) struct nd{ int lx,sm; nd operator*(const nd&G)const{ return {min(lx,sm+G.lx),sm+G.sm}; } }t[MAXN<<2],nt[MAXN<<2]; bool lz[MAXN<<2]; void pushup(int pos){ t[pos]=t[lson]*t[rson]; nt[pos]=nt[lson]*nt[rson]; } void upd(int pos){ lz[pos]^=1; swap(t[pos],nt[pos]); } void pushdown(int pos){ if(lz[pos])upd(lson),upd(rson),lz[pos]=0; } void build(int pos,int l,int r){ if(l==r){ t[pos]={a[l],a[l]}; nt[pos]={-a[l],-a[l]}; return; } int mid=(l+r)>>1; build(lson,l,mid),build(rson,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r){ upd(pos); return; } int mid=(l+r)>>1;pushdown(pos); if(ql<=mid)update(lson,l,mid,ql,qr); if(qr>mid)update(rson,mid+1,r,ql,qr); pushup(pos); } }T; void slv(){ n=read()+1; scanf("%s",s+1); for(int i=1;i<n;i++)a[i]=s[i]=='A'?1:-1; a[0]=1,a[n]=0; T.build(1,0,n); q=read(); while(q--){ int l=read()+1,r=read()+1; T.update(1,0,n,l,r); printf("%lld\n",(T.t[1].sm+n)/2-T.t[1].lx+1); } } signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); return 0; }