// 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]; 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; } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; cin >> q; for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; qu[r].push_back({l, i}); } int cur = 0, mn = 0; for (int i = 1; i <= n; i++) { if (a[i] == 'T') { s.push(i); upd(1, i, 1); } else { if (mn && !s.empty()) { mn--; cur--; upd(1, s.top(), -1); s.pop(); } cur++; } mn = min(mn + cur, cur); for (auto [a, b] : qu[i]) { ans[b] = qry(a); } } for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; }