/*
== ==
<^\()/^> <^\()/^>
\/ \/ \/ \/
/__\ . ' . /__\
== /\ . | . /\ ==
<^\()/^> !_\/ ' | ' \/_! <^\()/^>
\/ \/ !_/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);
}
}
std::vector<int> vote;
std::vector<std::array<int, 3>> query;
std::vector<std::pair<int, int>> st;
std::pair<int, int> combine(const std::pair<int, int> l,
const std::pair<int, int> r) {
return std::pair<int, int>(l.ff + r.ff, std::min(r.ss, l.ss + r.ff));
}
void upd(const int &id, const int &l, const int &r, const int &p,
const int &v) {
// std::cout << l << r << '\n';
if (l == r) {
st[id] = {v, v};
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] = combine(st[id << 1], st[id << 1 | 1]);
return;
}
std::pair<int, int> get(const int &id, const int &l, const int &r, const int &u,
const int &v) {
if (r < u || l > v)
return std::pair<int, int>(0, 0);
if (l >= u && r <= v)
return st[id];
int m = (l + r) >> 1;
return combine(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<std::pair<int, int>>((n << 2) + 1, {0, 0});
for (int i = 1; i <= n; i++) {
char c;
std::cin >> c;
vote.push_back((c == 'C') ? 1 : -1);
}
int q;
std::cin >> q;
for (int i = 0; i < q; i++) {
int l, r;
std::cin >> l >> r;
query.push_back({--l, --r, i});
}
std::sort(query.begin(), query.end(),
[&](const std::array<int, 3> &a, const std::array<int, 3> &b) {
return a[0] > b[0];
});
std::vector<int> ans(q);
int border = n - 1;
std::vector<int> cur;
for (const std::array<int, 3> &a : query) {
int l = a[0], r = a[1], id = a[2];
while (border >= l) {
if (vote[border] == -1) {
cur.push_back(border);
} else {
upd(1, 0, n - 1, border, 1);
if (!cur.empty()) {
int x = cur.back();
upd(1, 0, n - 1, x, -1);
cur.pop_back();
}
}
border--;
}
ans[id] = std::upper_bound(cur.rbegin(), cur.rend(), r) - cur.rbegin() -
get(1, 0, n - 1, l, r).ss;
}
for (int i = 0; i < q; i++) {
std::cout << ans[i] << '\n';
}
}
