#include <bits/stdc++.h>
using namespace std;
#define int int64_t
struct query {
int l, r, id;
query(int l, int r, int id) : l(l), r(r), id(id) {}
};
bool operator<(query const &a, query const &b) { return a.l > b.l; }
struct segtr {
struct node {
int tot, suf;
node(int tot = 0, int suf = 0) : tot(tot), suf(suf) {}
};
vector<node> tree;
node merge(node a, node b) {
if (a.suf == INT32_MAX)
return b;
else if (b.suf == INT32_MAX)
return a;
return node(a.tot + b.tot, min(a.suf + b.tot, b.suf));
}
void build(int ind, int l, int r, vector<int> const &a) {
if (l == r) {
tree[ind].tot = a[l];
tree[ind].suf = min(int(0), a[l]);
return;
}
int m = (l + r) >> 1;
build(ind << 1, l, m, a);
build(ind << 1 | 1, m + 1, r, a);
tree[ind] = merge(tree[ind << 1], tree[ind << 1 | 1]);
}
segtr(vector<int> const &a) : tree(a.size() << 2) {
build(1, 0, a.size() - 1, a);
}
node query(int ind, int l, int r, int tl, int tr) {
if (tl <= l && tr >= r)
return tree[ind];
if (tl > r || tr < l)
return {0, INT32_MAX};
int m = (l + r) >> 1;
node a = query(ind << 1, l, m, tl, tr),
b = query(ind << 1 | 1, m + 1, r, tl, tr);
return merge(a, b);
}
void update(int ind, int l, int r, int i, int val) {
if (i > r || i < l)
return;
if (l == r) {
tree[ind].tot = val;
tree[ind].suf = min(val, int(0));
return;
}
int m = (l + r) >> 1;
update(ind << 1, l, m, i, val);
update(ind << 1 | 1, m + 1, r, i, val);
tree[ind] = merge(tree[ind << 1], tree[ind << 1 | 1]);
}
};
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
char c;
cin >> c;
if (c == 'C')
a[i] = 1;
else
a[i] = -1;
}
int q;
cin >> q;
vector<query> quer;
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
l--;
r--;
quer.emplace_back(l, r, i);
}
vector<int> anses(q, 0);
sort(quer.begin(), quer.end());
segtr tr(a);
vector<int> st;
int curind = n;
for (int i = 0; i < q; i++) {
while (curind > quer[i].l) {
curind--;
if (a[curind] == 1) {
if (!st.empty()) {
tr.update(1, 0, n - 1, st.back(), -1);
st.pop_back();
}
} else {
tr.update(1, 0, n - 1, curind, 0);
st.push_back(curind);
}
}
int ans = upper_bound(st.begin(), st.end(), quer[i].r) - st.begin();
ans += -tr.query(1, 0, n - 1, quer[i].l, quer[i].r).suf;
anses[quer[i].id] = ans;
}
copy(anses.begin(), anses.end(), ostream_iterator<int>(cout, "\n"));
}
