#include<fstream>
#include<vector>
#include<deque>
#include<algorithm>
#include<iostream>
using namespace std;
//ifstream fi("election.in");
//ofstream fo("election.out");
char S[500005];
vector<pair<int,int> > Q[500005];
deque<int> Canceled;
int Rez[500005];
int MinSuf[2000005],Sum[2000005];
void update(int nod, int st, int dr, int poz, int val)
{
if(st==dr)
{
MinSuf[nod]=min(0,val);
Sum[nod]=val;
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
update(2*nod,st,mij,poz,val);
else
update(2*nod+1,mij+1,dr,poz,val);
Sum[nod]=Sum[2*nod]+Sum[2*nod+1];
MinSuf[nod]=min(MinSuf[2*nod+1],Sum[2*nod+1]+MinSuf[2*nod]);
}
int sumsuf;
int getDecalaj(int nod, int st, int dr, int l, int r)
{
if(l<=st && dr<=r)
{
int _sumsuf=sumsuf;
sumsuf+=Sum[nod];
return _sumsuf+MinSuf[nod];
}
int mij=(st+dr)/2;
int rez=0;
if(r>mij)
rez=min(rez,getDecalaj(2*nod+1,mij+1,dr,l,r));
if(l<=mij)
rez=min(rez,getDecalaj(2*nod,st,mij,l,r));
return rez;
}
int src(int poz)
{
int rez=-1;
for(int i=18; i>=0; i--)
{
if(rez+(1<<i)<Canceled.size() && Canceled[rez+(1<<i)]>poz)
rez+=(1<<i);
}
return Canceled.size()-rez-1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
cin>>(S+1);
int q;
cin>>q;
for(int i=1; i<=q; i++)
{
int x,y;
cin>>x>>y;
Q[x].push_back({y,i});
}
for(int i=n; i>=1; i--)
{
if(S[i]=='C')
{
update(1,1,n,i,1);
if(!Canceled.empty())
{
int last=Canceled.back();
Canceled.pop_back();
update(1,1,n,last,-1);
}
}
else
{
Canceled.push_back(i);
}
for(auto qry:Q[i])
{
int dr=qry.first;
int ind=qry.second;
sumsuf=0;
int stdr=src(dr);
int drst=-getDecalaj(1,1,n,i,dr);
Rez[ind]=stdr+drst;
}
}
for(int i=1; i<=q; i++)
cout<<Rez[i]<<"\n";
//fi.close();
//fo.close();
return 0;
}
