//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 5e5 + 1;
int n, q, res[N + 1];
int pref[N + 1], suf[N + 1], a[N + 1];
vector<pair<int, int> > query[N + 1];
struct SegmentTree
{
int tree[4 * N + 1], lazy[4 * N + 1];
void buildtree(int v, int TreeL, int TreeR)
{
if (TreeL == TreeR)
{
tree[v] = suf[TreeL];
return ;
}
int mid = (TreeL + TreeR)/2;
buildtree(v * 2, TreeL, mid);
buildtree(v * 2 + 1, mid + 1, TreeR);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
void push(int v)
{
if (!lazy[v])
{
return ;
}
int d = lazy[v];
lazy[v] = 0;
lazy[2 * v] += d;
lazy[2 * v + 1] += d;
tree[2 * v] += d;
tree[2 * v + 1] += d;
}
void add(int v, int TreeL, int TreeR, int L, int R, int val)
{
if (L > R)
{
return ;
}
if (TreeL == L && TreeR == R)
{
tree[v] += val;
lazy[v] += val;
return ;
}
int mid = (TreeL + TreeR)/2;
push(v);
add(v * 2, TreeL, mid, L, min(R, mid), val);
add(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, val);
tree[v] = min(tree[2 * v], tree[2 * v + 1]);
}
int get(int v, int TreeL, int TreeR, int L, int R)
{
if (L > R)
{
return 1e9;
}
if (TreeL == L && TreeR == R)
{
return tree[v];
}
int mid = (TreeL + TreeR)/2;
push(v);
return min(get(v * 2, TreeL, mid, L, min(R, mid)), get(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R));
}
} tree;
void read()
{
cin >> n;
for (int i = 1; i <= n; ++ i)
{
char c;
cin >> c;
a[i] = (c == 'C' ? 1 : -1);
pref[i] = pref[i - 1] + a[i];
}
for (int i = n; i >= 1; -- i)
{
suf[i] = suf[i + 1] + a[i];
}
tree.buildtree(1, 1, n + 1);
}
void solve()
{
cin >> q;
for (int i = 1; i <= q; ++ i)
{
int l, r;
cin >> l >> r;
query[l].emplace_back(r, i);
}
vector<int> st;
for (int l = n; l >= 0; -- l)
{
while(!st.empty() && pref[l] <= pref[st.back()])
{
tree.add(1, 1, n + 1, 1, st.back(), -1);
st.pop_back();
}
for (auto [r, i] : query[l + 1])
{
res[i] += upper_bound(st.rbegin(), st.rend(), r) - st.rbegin();
int t = tree.get(1, 1, n + 1, l + 1, r) - tree.get(1, 1, n + 1, r + 1, r + 1);
res[i] += max(0, -t);
}
st.push_back(l);
tree.add(1, 1, n + 1, 1, l, 1);
}
for (int i = 1; i <= q; ++ i)
{
cout << res[i] << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}
