// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; stack <int> s; char a[500005]; vector <pair <int, int> > qu[500005]; int ft[500005], ans[500005], prv[500005], nxt[500005]; int n, q; void upd (int l, int r, int v) { for (; l <= n; l += (l & -l)) ft[l] += v; r++; for (;r <= n; r += (r & -r)) ft[r] -= v; } int qry (int p) { int res = 0; for (;p;p-=(p & -p)) res += ft[p]; return res; } struct node{ int s, e, m, sm, suf; node *l, *r; node (int _s, int _e) { s = _s, e = _e, m = (s + e) >> 1; if (s != e)l = new node(s, m), r = new node(m + 1, e); sm = suf = 0; } void upd (int p, int v) { if (s == e) sm = suf = v; else { if (p <= m) l->upd(p, v); else r->upd(p, v); sm = l->sm + r->sm; suf = min(r->suf, r->sm + l->suf); } } pair <int, int> qry (int a, int b) { if (a == s && b == e) return {suf, sm}; else if (b <= m) return l->qry(a, b); else if (a > m) return r->qry(a, b); else { pair <int, int> tmp = r->qry(m + 1, b), tmp2 = l->qry(a, m); return {min(tmp.second, tmp.first + tmp2.second), tmp.second + tmp2.second}; } } }*root; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; nxt[n + 1] = n + 1; for (int i = n; i >= 1; i--) { nxt[i] = nxt[i + 1]; if (a[i] == 'C') nxt[i] = i; } cin >> q; for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; qu[r].push_back({l, i}); } root = new node(1, n); int cur = -1, mn = 0; for (int i = 1; i <= n; i++) { if (a[i] == 'T') { s.push(i); prv[i] = prv[i - 1]; upd(1, i, 1); } else { if (!s.empty()) { int lo = 1, hi = s.top()-1, v = lo - 1; while (lo <= hi) { int mid = (lo + hi) >> 1; if (root->qry(1, mid).first + root->qry(mid + 1, nxt[s.top()] - 1).second > 0) v = mid, lo = mid + 1; else hi = mid - 1; } cur = s.top(); //cout << v << ' ' << root->qry(4, 9).first << '\n'; mn--; upd(1, v, -1); root->upd(s.top(), -1); s.pop(); } root->upd(i, 1); prv[i] = i; mn = min(mn + 1, 1); } for (auto [a, b] : qu[i]) { ans[b] = qry(a); } } for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; }