#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 100;
int a[maxn];
struct Node
{
int L, R, mid, lazy;
pair <int, int> v;
Node *lc, *rc;
Node(int l, int r)
{
L = l, R = r, mid = (L + R) / 2, v = {0, L}, lc = rc = NULL;
return ;
}
void init()
{
if (R - L == 1)
{
return ;
}
lc = new Node(L, mid);
rc = new Node(mid, R);
lc->init();
rc->init();
return ;
}
void spread()
{
v.first += lazy;
if (lc)
{
lc->lazy += lazy;
rc->lazy += lazy;
}
lazy = 0;
return ;
}
void update(int l, int r, int val)
{
spread();
if (L == l and R == r)
{
lazy = val;
spread();
return ;
}
if (l < mid)
{
lc->update(l, min(r, mid), val);
}
if (r > mid)
{
rc->update(max(l, mid), r, val);
}
lc->spread();
rc->spread();
v = min(lc->v, rc->v);
}
pair <int, int> get(int l, int r)
{
spread();
if (l == L and r == R)
{
return v;
}
pair <int, int> ret = {maxn, 0};
if (l < mid)
{
ret = min(ret, lc->get(l, min(r, mid)));
}
if (r > mid)
{
ret = min(ret, rc->get(max(l, mid), r));
}
return ret;
}
pair <int, int> bsss()
{
spread();
if (R - L == 1)
{
return v;
}
lc->spread();
rc->spread();
if (lc->v.first < 0)
{
return lc->bsss();
}
return rc->bsss();
}
pair <int, int> bs(int l, int r)
{
spread();
if (l >= r or v.first >= 0)
{
return {maxn, 0};
}
if (l == L and R == r)
{
return bsss();
}
pair <int, int> tmp = lc->bs(l, min(mid, r));
if (tmp.second)
{
return tmp;
}
return rc->bs(max(l, mid), r);
}
};
vector <pair <int, int>> qs[maxn];
int ans[maxn];
vector <int> bp;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n;i++)
{
char inp;
cin >> inp;
a[i] = (inp == 'C') * 2 - 1;
}
a[0] = 1;
Node *lr = new Node(0, n + 1), *rr = new Node(0 , n + 1);
lr->init();
rr->init();
for (int i = 0;i <= n;i++)
{
lr->update(i, n + 1, a[i]);
rr->update(1, i + 1, a[i]);
}
int q;
cin >> q;
for (int i = 1;i <= q;i++)
{
int l, r;
cin >> l >> r;
qs[l].push_back({r, i});
}
int s = 0;
for (int i = 0;i <= n;i++)
{
s += a[i];
if (s < 0)
{
s++;
bp.push_back(-i);
rr->update(1, i + 1, 1);
}
}
reverse(bp.begin(), bp.end());
for (int i = 1;i <= n;i++)
{
lr->update(i, n + 1, -a[i - 1]);
if (a[i - 1] == -1 and bp.size())
{
bp.pop_back();
}
if (a[i - 1] == 1)
{
int ind = lr->bs(i, n + 1).second;
if (ind)
{
bp.push_back(-ind);
rr->update(1, ind + 1, 1);
}
}
for (auto o : qs[i])
{
int r = o.first, aq = o.second;
int rans = bp.end() - lower_bound(bp.begin(), bp.end(), -r);
int ind = rr->get(i, r + 1).second;
int tmp2 = 0;
if (r != n)
{
tmp2 = rr->get(r + 1, r + 2).first;
}
rans += max(0, -rr->get(i, r + 1).first + tmp2);
ans[aq] = rans;
}
}
for (int i = 1;i <= q;i++)
{
cout << ans[i] << '\n';
}
}
