#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int maxn=2e5+10; int n;string s; struct node{ int pre,sm; }; node operator+(node a,node b){return {min(a.pre,a.sm+b.pre),a.sm+b.sm};} struct tree{ struct nd{ node a,b;int lz; void upd(){lz^=1,swap(a,b);} }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void pu(int p){d[p].a=d[ls(p)].a+d[rs(p)].a,d[p].b=d[ls(p)].b+d[rs(p)].b;} void pd(int p){if(!d[p].lz)return;d[ls(p)].upd(),d[rs(p)].upd(),d[p].lz=0;} void bd(int l,int r,int p){ if(l==r){ if(s[l]=='A')d[p].a={0,1},d[p].b={-1,-1}; else d[p].a={-1,-1},d[p].b={0,1}; return; }int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); } void modify(int l,int r,int s,int t,int p){ if(l<=s&&t<=r)return d[p].upd(),void();pd(p); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p));if(r>mid)modify(l,r,mid+1,t,rs(p));pu(p); } }t; void slv(){ n=read();cin>>s;s="B"+s+"A";t.bd(0,n+1,1); for(int l,r,q=read();q;q--){ l=read(),r=read(),t.modify(l+1,r+1,0,n+1,1); printf("%d\n",(t.d[1].a.sm+n+2)/2-t.d[1].a.pre-1); } } int main(){ // freopen("medium.in","r",stdin),freopen("medium.out","w",stdout); slv(); return 0; }