/*
== ==
<^\()/^> <^\()/^>
\/ \/ \/ \/
/__\ . ' . /__\
== /\ . | . /\ ==
<^\()/^> !_\/ ' | ' \/_! <^\()/^>
\/ \/ !_/I_|| . ' \'/ ' . ||_I\_! \/ \/
/__\ /I_/| || -==C++==- || |\_I\ /__\
/_ \ !//| | || ' . /.\ . ' || | |\\! /_ \
(- ) /I/ | | || . | . || | | \I\ (= )
\__/!//| | | || ' | ' || | | |\\!\__/
/ \I/ | | | || ' . ' * || | | | \I/ \
{_ __} | | | || || | | | {____}
_!__|= || | | | || * + || | | | || |__!_
_I__| ||__|__|__|_|| A ||_|__|__|__||- |__I_
-|--|- ||--|--|--|-|| __/_\__ * ||-|--|--|--||= |--|-
| | || | | | || /\-'o'-/\ || | | | || | |
| |= || | | | || _||:<_>:||_ || | | | ||= | |
| |- || | | | || * /\_/=====\_/\ * || | | | ||= | |
| |- || | | | || __|:_:_[I]_:_:|__ || | | | ||- | |
_|__| ||__|__|__|_||:::::::::::::::::::::||_|__|__|__|| |__|_
-|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
jgs|- || | | | ||:::::::::::::::::::::|| | | | ||= | |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include "bits/stdc++.h"
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int, int>
#define mp make_pair
void setIO(std::string s = "") {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
if (!s.empty()) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
}
struct node {
int sfx, sum;
node() { sfx = sum = 0; }
};
struct query {
int l, r, id;
query(int lll, int rr, int idd) : l(lll), r(rr), id(idd) {}
friend bool operator<(const query &dis, const query &other) {
return dis.l > other.l;
}
};
std::vector<node> st;
node comb(const node &l, const node &r) {
node ret;
ret.sum = l.sum + r.sum;
ret.sfx = std::min(l.sfx + r.sum, r.sfx);
return ret;
}
void upd(const int &id, const int &l, const int &r, const int &p,
const int &v) {
if (l == r) {
st[id].sum = v;
st[id].sfx = std::min(v, 0);
return;
}
int m = (l + r) >> 1;
if (p <= m)
upd(id << 1, l, m, p, v);
else
upd((id << 1) | 1, m + 1, r, p, v);
st[id] = comb(st[id << 1], st[(id << 1) | 1]);
return;
}
node get(const int &id, const int &l, const int &r, const int &u,
const int &v) {
// std::cout << id << ' ' << l << ' ' << r << ' ' << u << ' ' << v << '\n';
if (l > v || r < u) {
node ret;
ret.sfx = ret.sum = 0;
return ret;
}
if (l >= u && r <= v)
return st[id];
int m = (l + r) >> 1;
return comb(get(id << 1, l, m, u, v), get((id << 1) | 1, m + 1, r, u, v));
}
int main() {
setIO();
int n;
std::cin >> n;
st = std::vector<node>((n << 2) + 5);
std::string s;
std::cin >> s;
std::vector<int> vote;
for (const char &c : s)
vote.push_back(c == 'C' ? 1 : -1);
for (int i = 0; i < n; i++)
upd(1, 0, n - 1, i, 1);
int q;
std::cin >> q;
std::vector<query> queries;
for (int i = 0; i < q; i++) {
int l, r;
std::cin >> l >> r;
query qq(--l, --r, i);
queries.push_back(qq);
}
std::sort(queries.begin(), queries.end());
int done = 0;
std::vector<int> tony;
std::vector<int> ans(q);
for (int i = n - 1; i >= 0; i--) {
if (vote[i] == -1) {
tony.push_back(i);
upd(1, 0, n - 1, i, 0);
} else {
if (!tony.empty()) {
int sw = tony.back();
upd(1, 0, n - 1, sw, -1);
tony.pop_back();
}
}
while (done < q && queries[done].l >= i) {
const query &qq = queries[done];
ans[qq.id] = (int)(std::upper_bound(tony.rbegin(), tony.rend(), qq.r) -
tony.rbegin()) -
get(1, 0, n - 1, 0, qq.r).sfx;
// std::cout << get(1, 0, n - 1, 0, qq.r).sfx << std::endl;
done++;
}
}
for (int i = 0; i < q; i++)
std::cout << ans[i] << '\n';
}
