#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int inf = 1e9;
const int maxn = 500005;
const int maxq = 500005;
struct Node {
int sum, msuf;
};
int n, q;
int a[maxn];
Node tree[4*maxn];
int answer[maxq];
int ql[maxq], qr[maxq];
vector<int> query[maxn]; // query[i] = ids of queries such that L=i
void merge(Node& v, Node& l, Node& r) {
v.sum = l.sum + r.sum;
v.msuf = min(l.msuf + r.sum, r.msuf);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v].sum = a[tl];
tree[v].msuf = min(0, a[tl]);
return;
}
int tm = (tl + tr) / 2;
build(2*v, tl, tm);
build(2*v+1, tm+1, tr);
merge(tree[v], tree[2*v], tree[2*v+1]);
}
void update(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
tree[v].sum = val;
tree[v].msuf = min(0, val);
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(2*v, tl, tm, pos, val);
} else {
update(2*v+1, tm+1, tr, pos, val);
}
merge(tree[v], tree[2*v], tree[2*v+1]);
}
int get_sum(int v, int tl, int tr, int l, int r) {
if (l > r) {
return 0;
}
if (l <= tl && tr <= r) {
return tree[v].sum;
}
int tm = (tl + tr) / 2;
return get_sum(2*v, tl, tm, l, min(r, tm))
+ get_sum(2*v+1, tm+1, tr, max(l, tm+1), r);
}
inline void print(int v) {
while (v > 1) {
cout << " ";
v /= 2;
}
}
int min_suffix(int v, int tl, int tr, int l, int r) {
// print(v);
// cout << "min_suffix(v=" << v << ", tl=" << tl << ", tr=" << tr << ", l=" << l << ", r=" << r << ")" << endl;
if (l > r) {
// print(v);
// cout << "res=" << inf << endl;
return inf;
}
if (l <= tl && tr <= r) {
// print(v);
// cout << "res=" << tree[v].msuf << endl;
return tree[v].msuf;
}
int tm = (tl + tr) / 2;
int res1 = min_suffix(2*v, tl, tm, l, min(r, tm))
+ get_sum(2*v+1, tm+1, tr, max(l, tm+1), r);
int res2 = min_suffix(2*v+1, tm+1, tr, max(l, tm+1), r);
// print(v);
// cout << "res1=" << res1 << " res2=" << res2 << endl;
return min(res1, res2);
}
int main() {
// ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
char ch;
cin >> ch;
a[i] = (ch == 'C') ? 1 : -1;
}
cin >> q;
for (int i = 1; i <= q; ++i) {
cin >> ql[i] >> qr[i];
query[ql[i]].push_back(i);
}
build(1, 1, n);
vector<int> stk; // which positions should be removed (decreasing order)
for (int L = n; L >= 1; --L) {
// cout << "L=" << L << endl;
if (a[L] == 1 && !stk.empty()) {
int i = stk.back();
stk.pop_back();
update(1, 1, n, i, a[i]); // original value
// cout << "removed " << i << " from stack, updated a[" << i << "] to " << a[i] << endl;
} else if (a[L] == -1) {
stk.push_back(L);
update(1, 1, n, L, 0); // set it to 0
// cout << "added " << L << " to stack, updated a[" << L << "] to " << 0 << endl;
}
for (int i : query[L]) {
int R = qr[i];
auto it = upper_bound(stk.rbegin(), stk.rend() , R);
answer[i] = 0;
answer[i] += distance(stk.rbegin(), it); // which votes will be removed by pass from L to R
int min_suffix_here = min_suffix(1, 1, n, L, R);
answer[i] += -min_suffix_here; // which will be removed from R to L (assuming the previous pass was done)
// cout << "processing query " << i << " (L=" << L << ", R=" << R << ")" << endl;
// cout << "it distance=" << distance(stk.rbegin(), it) << ", min suffix=" << min_suffix_here << endl;
// cout << endl;
}
}
for (int i = 1; i <= q; ++i) {
cout << answer[i] << '\n';
}
}
