//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define all(c) (c).begin(),(c).end()
// if you're reading this i hope to meet you in IOI 2021
// RECHECK CONSTRAINTS AFTER MAKING A REDUCTION
struct Segtree {
int n;
vector<int> seg, lazy;
Segtree(int n) : n(n), seg(4*n), lazy(4*n) {}
void build(vector<int>& arr, int v, int vl, int vr) {
if (vr-vl == 1)
seg[v] = arr[vl];
else {
int vm = vl+vr>>1;
build(arr, v<<1, vl, vm);
build(arr, v<<1|1, vm, vr);
seg[v] = min(seg[v<<1], seg[v<<1|1]);
}
}
void build(vector<int>& arr) {
build(arr, 1, 0, n);
}
void push(int v) {
seg[v<<1] += lazy[v];
lazy[v<<1] += lazy[v];
seg[v<<1|1] += lazy[v];
lazy[v<<1|1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int vl, int vr, int l, int r, int x) {
if (l >= r) return;
if (l == vl and r == vr)
seg[v] += x, lazy[v] += x;
else {
push(v);
int vm = vl+vr>>1;
update(v<<1, vl, vm, l, min(r, vm), x);
update(v<<1|1, vm, vr, max(l, vm), r, x);
seg[v] = min(seg[v<<1], seg[v<<1|1]);
}
}
void update(int l, int r, int x) {
update(1, 0, n, l, r, x);
}
int query(int v, int vl, int vr, int l, int r) {
if (l >= r) return INT_MAX;
if (l <= vl and vr <= r) return seg[v];
push(v);
int vm = vl+vr>>1;
return min(query(v<<1, vl, vm, l, min(r, vm)), query(v<<1|1, vm, vr, max(l, vm), r));
}
int query(int l, int r) {
return query(1, 0, n, l, r);
}
};
signed main() {
// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
char c;
cin >> c;
arr[i] = (c == 'C' ? 1 : -1);
}
cin >> q;
vector<int> res(q);
vector<vector<array<int, 2>>> qs(n+1);
Segtree rmq(n+1); // [i] = balance after i elements, RMQ and range add update
for (int qq = 0; qq < q; qq++) {
int l, r;
cin >> l >> r; l--;
qs[r].push_back({l, qq});
}
vector<int> ts;
for (int r = 0; r <= n; r++) {
for (auto [l, qq] : qs[r]) {
res[qq] = rmq.query(l, l+1) - rmq.query(l, r+1) + (ts.end() - lower_bound(all(ts), l));
}
if (r < n) {
if (arr[r] == -1)
ts.push_back(r);
else {
if (ts.size())
rmq.update(ts.back()+1, n+1, -1), ts.pop_back();
rmq.update(r+1, n+1, 1);
}
}
}
for (int e : res) cout << e << endl;
}
/* --- PSolving ---
* Simplifying (getting rid of variables, conditions, code logic, etc.)
* Reframing
* Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
* Inducing
* Divide and conquer
* Working backwards
* Visual intuition
* !! Reductions don't have to be specializations, they can be generalizations
*/
