#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct node {
int sum, min_val;
};
void merge_node(node &t, node &a, node &b)
{
t.sum = a.sum + b.sum;
t.min_val = min(b.min_val, a.min_val + b.sum);
}
struct seggy{
vector<node> t; int n;
seggy(int N) : n(1<<(__lg(N - 1) + 1)) {
t.resize(2*n, {0, 0});
}
int get() {return t[1].min_val;}
void upd(int idx, int n_val) {
for (idx += n, t[idx].sum = n_val, t[idx].min_val = min(0, n_val), idx /= 2; idx > 0; idx /= 2)
merge_node(t[idx], t[idx * 2], t[idx * 2 + 1]);
}
};
const int BLOCK_SIZE = 300;
struct query {
int l, r, id;
query() {}
query(int l, int r, int id) : l(l), r(r), id(id) {}
bool operator<(const query& b) const {
if (l / BLOCK_SIZE == b.l / BLOCK_SIZE)
return r < b.r;
return l/BLOCK_SIZE < b.l /BLOCK_SIZE;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> arr(n + 1), pref(n + 1);
string S;
cin >> S;
int OFFSET = n + 5;
vector<vector<int> > idxs(n * 2 + 10);
for (int i = 0; i < S.size(); i++) {
if (S[i] == 'C')
arr[i + 1] = 1;
else
arr[i + 1] = -1;
pref[i + 1] = arr[i + 1] + pref[i];
idxs[pref[i + 1] + OFFSET].push_back(i);
}
int q;
cin >> q;
vector<query> queries(q);
for (int i = 0; i < q; i++)
{
cin >> queries[i].l >> queries[i].r;
queries[i].id = i;
}
sort(all(queries));
int L = 1, R = 1;
deque<int> imp;
seggy seg(n + 1);
if (arr[1] != -1)
seg.upd(1, arr[1]);
else
imp.push_back(1);
vector<int> out(n);
for (auto [l, r, id] : queries) {
while (l < L) { // move by one to the left
seg.upd(L - 1, arr[L - 1]);
// need to get new pref
if (pref[L - 2] > pref[L - 1]) { // in this case we need to see where pref - 1 is
int searched = pref[L - 2] - 1;
int next_beg = lower_bound(all(idxs[searched]), L - 1) - idxs[searched].begin();
if (next_beg == -1 || next_beg == idxs[searched].size()) {
// doesnt exist
} else {
imp.push_front(idxs[searched][next_beg]);
seg.upd(idxs[searched][next_beg], 0);
}
} else if (pref[L - 2] < pref[L - 1]) {
if (!imp.empty()) {
seg.upd(imp.front(), arr[imp.front()]);
imp.pop_front();
}
}
L--;
}
while (r > R) {
seg.upd(R + 1, arr[R + 1]);
if (!imp.empty() and pref[R + 1] == imp.back() - 1) {
seg.upd(R + 1, 0);
imp.push_back(R + 1);
}
R++;
}
while (l > L) {
seg.upd(L - 1, 0);
if (!imp.empty() and imp.front() == L - 1)
imp.pop_front();
if (pref[L - 1] > pref[L]) { // novi je pref [L], tako da ovo znaci da smo izgubili + i eventualno dodajemo novi
int searched = pref[L] - 1;
int next_beg = lower_bound(all(idxs[searched]), L) - idxs[searched].begin();
if (next_beg == -1 || next_beg == idxs[searched].size()) {
// doesnt exist
} else {
imp.push_front(idxs[searched][next_beg]);
seg.upd(idxs[searched][next_beg], 0);
}
} else {
if (!imp.empty()) {
if (imp.front() == pref[L - 1] - 1)
imp.pop_front();
}
}
L++;
}
while (r < R) {
seg.upd(R, 0);
if (!imp.empty() and imp.back() == R)
imp.pop_back();
R--;
}
int val = imp.size() - min(0, seg.t[1].min_val);
out[id] = val;
}
for (int i = 0; i < q; i++)
cout << out[i] << "\n";
}
