#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }
using ll = long long;
using pii = std::pair<int, int>;
const int NMAX = 5e5;
using namespace std;
vector<pii>qu[NMAX + 5];
vector<int>stk;
char ch;
int a[NMAX + 5], ans[NMAX + 5], n, q;
///cate numere din stk sunt >= l
inline int cate(int l){
if (stk.empty()) return 0;
auto it = lower_bound(all(stk), l);
return distance(it, stk.end());
}
struct Node{
int sum;
int min_suf;
Node () : sum(0), min_suf(INT_MAX) {}
Node (int x) : sum(x), min_suf(x) {}
static Node merge(const Node& left, const Node& right){
if (left.min_suf == INT_MAX) return right;
if (right.min_suf == INT_MAX) return left;
Node aux;
aux.sum = left.sum + right.sum;
aux.min_suf = min(right.min_suf, right.sum + left.min_suf);
return aux;
}
};
struct ST{
Node aint[4 * NMAX + 5];
void build(int nod = 1, int st = 1, int dr = n){
if (st == dr){
aint[nod] = Node(a[st]);
return;
}
int m = (st + dr) >> 1;
build(2 * nod, st, m);
build(2 * nod + 1, m + 1, dr);
aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
}
void update(int pos, int val, int nod = 1, int st = 1, int dr = n){
if (st == dr){
aint[nod] = Node(val);
return;
}
int m = (st + dr) >> 1;
if (pos <= m)
update(pos, val, 2 * nod, st, m);
else
update(pos, val, 2 * nod + 1, m + 1, dr);
aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
}
Node query(int l, int r, int nod = 1, int st = 1, int dr = n){
if (st > r || dr < l) return Node();
if (l <= st && dr <= r) return aint[nod];
int m = (st + dr) >> 1;
return Node::merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
}
}aint;
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> ch;
a[i] = (ch == 'C' ? 1 : -1);
}
cin >> q;
for (int i = 1, l, r; i <= q; ++i){
cin >> l >> r;
qu[r].push_back({l, i});
}
aint.build();
for (int i = 1; i <= n; ++i){
if (a[i] == -1) {
aint.update(i, 0);
stk.push_back(i);
}
if (a[i] == 1 && !stk.empty()) {
aint.update(stk.back(), -1);
stk.pop_back();
}
for (auto &[l, idx] : qu[i])
ans[idx] = cate(l) + abs(min(0LL, aint.query(l, i).min_suf));
}
for (int i = 1; i <= q; ++i)
cout << ans[i] << '\n';
return 0;
}
