#include <bits/stdc++.h>
#ifdef LOCAL
#include "../../debug.h"
#else
#define debug(...) ((void)0)
#endif
using namespace std;
using ll = long long;
// #define int ll
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using pii = pair<int,int>;
struct Node {
ll sm;
ll lz;
ll rz;
ll ans;
};
Node combine(const Node& a, const Node& b) {
Node c;
c.sm = a.sm + b.sm;
c.lz = min(a.lz, a.sm + b.lz);
c.rz = min(b.rz, b.sm + a.rz);
c.ans = min({ a.ans + b.sm, a.sm + b.ans, a.lz + b.rz });
return c;
}
const Node identity_node = {0, 0, 0, 0};
class SegmentTree {
private:
vector<Node> tree;
string s;
int n;
void build(int u, int l, int r) {
if (l == r) {
if (s[l] == 'C') {
tree[u].sm = 1;
tree[u].lz = 0;
tree[u].rz = 0;
tree[u].ans = 0;
} else {
tree[u].sm = -1;
tree[u].lz = -1;
tree[u].rz = -1;
tree[u].ans = -1;
}
return;
}
int mid = (l + r) >> 1;
build(u*2, l, mid);
build(u*2+1, mid+1, r);
tree[u] = combine(tree[u*2], tree[u*2+1]);
}
Node query(int u, int l, int r, int ql, int qr) {
if (qr < l || r < ql) {
return identity_node;
}
if (ql <= l && r <= qr) {
return tree[u];
}
int mid = (l + r) >> 1;
Node left_node = query(u*2, l, mid, ql, qr);
Node right_node = query(u*2+1, mid+1, r, ql, qr);
if (qr <= mid) {
return left_node;
} else if (ql > mid) {
return right_node;
} else {
return combine(left_node, right_node);
}
}
public:
SegmentTree(const string& str) {
s = str;
n = (int)s.size();
tree.resize(4 * n);
build(1, 0, n-1);
}
int query_range(int l, int r) {
Node res = query(1, 0, n-1, l, r);
return -res.ans;
}
};
void solve() {
int n; cin >> n;
string votes; cin >> votes;
SegmentTree segTree(votes);
int q; cin >> q;
while (q--) {
int L, R;
cin >> L >> R;
L--; R--;
cout << segTree.query_range(L, R) << '\n';
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
