#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define compact(v) v.erase(unique(all(v)) , v.end())
#define pi pair<int , int>
#define vi vector<int>
#define eb emplace_back
#define FOR(i , l , r) for(int i = l; i <= r; ++ i)
#define FORD(i , l , r) for(int i = l; i >= r; -- i)
using namespace std;
typedef long long ll;
const int nd = 1e5 + 1 , mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);
template <class T> bool maximize(T &a , T b){return (a < b ? a = b , true : false);}
template <class T> bool minimize(T &a , T b){return (a > b ? a = b , true : false);}
int add(int a , int b) {return (a + b) % mod;}
int mul(int a , int b) {return (a * b) % mod;}
int sub(int a , int b) {return (a - b + mod) % mod;}
int xpow(int a , int b){
int res = 1;
for(int i = 0; (1 << i) <= b; ++ i){
if(b & (1 << i)) res = mul(res , a);
a = mul(a , a);
}
return res;
}
int pref[nd] , suf[nd];
struct SMT{
int st[4 * nd];
void init(int n){
FOR(i , 0 , 4 * (n + 5)) st[i] = 1e9;
}
void up(int id , int l , int r , int x , int v){
if(l > x || r < x) return;
if(l == r){
st[id] = min(st[id] , v);
return;
}
int mid = (r + l) >> 1;
up(id * 2 , l , mid , x , v);
up(id * 2 + 1 , mid + 1 , r , x , v);
st[id] = min(st[id * 2] , st[id * 2 + 1]);
}
int get(int id , int l , int r , int a , int b){
if(l > b || r < a) return 1e9;
if(a <= l && r <= b) return st[id];
int mid = (r + l) >> 1;
return min(get(id * 2 , l , mid , a , b) , get(id * 2 + 1 , mid + 1 , r , a , b));
}
} seg[2];
int par[20][nd];
void init(int n){
FOR(i , 1 , 19){
FOR(j , 1 , n){
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
}
int get(int p , int mask){
while(mask){
int bit = 31 - __builtin_clz(mask);
p = par[bit][p];
mask ^= (1 << bit);
}
return p;
}
char a[nd];
vi pos_T;
void solve(){
int n;
cin >> n;
seg[0].init(n) , seg[1].init(n);
FOR(i , 1 , n) cin >> a[i];
int delta = 0;
int delta_suf = 0;
int pre = 0;
FOR(i , 1 , n){
if(a[i] == 'T'){
if(pre) par[0][pre] = i;
pos_T.eb(i);
pre = i;
}
delta += 1 - 2 * (a[i] == 'T');
pref[i] = delta;
seg[0].up(1 , 1 , n , i , delta);
delta_suf += 1 - 2 * (a[n - i + 1] == 'T');
suf[i] = delta_suf;
seg[1].up(1 , 1 , n , i , delta_suf);
}
init(n);
int q;
cin >> q;
while(q --){
int l , r;
cin >> l >> r;
int v = seg[0].get(1 , 1 , n , l , r) - pref[l - 1];
int p = l;
int res = 0;
if(v < 0){
res = - v;
p = *lower_bound(all(pos_T) , l);
p = get(p , -v - 1);
}
int v2 = seg[1].get(1 , 1 , n , n - r + 1 , n - p) - suf[n - r];
if(v2 >= 0){
cout << res << '\n';
continue;
}
cout << res - v2 << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#define task "panh"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test_case = 1;
while(test_case --) solve();
return 0;
}
/*
-. ::. -: .::::::::::
***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######:
**##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%#+########+*@%@#*##+=@%######:
#%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%#=+###*##*+#@##@%###+=%#####:
#####***%##@%+***#%#++#######*********++***#*#+##%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%#+*######*+%###@###*=#%####:
##*****####@*+***###+=**#+==*+*###%#%###%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%*#*+%###:
%##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###:
*####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##:
#**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%*%+*####****@######%**#%#:
####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%@@%#####=%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###.
###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%*##*#**##**+@#######@**##:
###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##.
###*#%#%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%#######@+##:
###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%:
##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@ @@@=-=+##@%=##+#*#***#%###########.
##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%=******+*****=#@@ @@@*:-#@%+=%+#*###+#@###########:
:@#*#%##%#**##+#%+************#*****++***+#*+-%@==+++*=+@=++++==@ @@#%=##%==+*++*+*****=#@@ @@@@#*#@*-@+***##+#%########%#:
#@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%-==**#@@@@@@##%+#%-=+++++**+**==@@ @#*+@*=##***##+*@###########:
@*%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@ @@#####@#=++**+******-@= *@@@@@@@@@@@=+#****#*+@###########:
@@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@ @@######@+=+++++++*++=@ @@@@@@@@ +@@=+#****#*=%##########:
#@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@ .. @@#####%@-=***+*****=@@@@@@ .@@.@ @#=***#+#*=@@##########:
@%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@ .: @@#####@@=+++++*++**=@@%@@@ -@@@:*@=*#**+#*+@*@#########:
=: ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@ .. #@@#####@#=+**+*+#@@%#@##@@ @ @-=@=****+%*=@-#@%#######:
: :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@ -*+ =@@#####@*=+**++#= -@% : @% -@==@=#***+@*=@% +@@######:
@@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*. *:: -@@*####%#-++++##=:% @-@@% *@=-@=#***+@+=%@@. @@@%###:
+@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@# @@####%*-=+++#+=@@ : +@+=@+#**++@+=@#%@%- -##%:
##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@ @@@*##%##===++**#@ .. :@*-@%***+*@==@###%@@%####:
###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@ ::++ =@@***#*#=-==++=@@ @#=#@*+*=#%==@@%#*###%@##.
#*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@ @@@*+%##*--=+==@+ . @@+#@*=+=@#==@###%#####.
**@ @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@ @ @@ @@@+*#+**:-==*@ . @@**@+=+*%#=+@###########.
++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@ @@ . . @@@@#=+**=--#@ +@**@+==##*-#@###########:
-@@@ @#-======%@*===*###@@@@#=----==+==-=#@@@@ @@* :@= @@@@@#*#=:#@ @*#@==+%#+*#@%##########:
%@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@ ::.+@#: :#@@@@#+#@@ @#@@--%#=#*%###########:
%@@ @%@#%##++======------=========#%@@@@=====*=@#%@@%- ... @@@@@@@@# @*@#:=@#**#*@###########.
@@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@ . . .*% @@@:-@##=#+#@#%#########.
@@@**=@++++=:=%##@@@##%##*+==@%==++******+*#@ .. . # @@*:##**##+#%##########%.
+@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@= . .. =. @@@.:@*#*##+@%###########
:%#**#%@=**+=%###@@+@#%++******=*@@#=********+%@@ . @@.:@**###*+@###*%#######.
:#+*##@%+**=%###*@+##@#%*=*#***+=@%@++******+++@@ @@:.@@=#**#=@@############.
++##%@*++=#@###*%@*##@##%#=+****=#%#=**+*****+%@ @@.=@@@=*##*=@######%######
#%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+ . @@.#%#@%=###=#%#%####%######
:@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@ @ %@@@##@@++##=-@###%##########
+-=@@=+@%####*%###%@*##%==+=#%#%+=+*****==@ :=-:: @@@@*#%#@=*#+-@########=@#####
**%@#*%####*#@%@*%#%##@#*##%@*==+%###@*=+*++*+-@@ ::: @@%#@###%+#=.@%########+%#####
#@@########*@@@@%:@%###@%####%@+:##@##%*=+*+++==@ :@@%@####@**-:@%######%*#*######
@%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@ @@ =@@%######@@+ =@%#################
=%#######+@@##@#+*=@##%####@%##############@=======@ @%@-@@@#######@%: @@##########%#*######
.######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@ :. **@@:@@@#####@# +@%#############*######
.#%##+@@@%=#%@#*#**@#%####@:=%@##%##*######*##@*=-==#@ :=@@: @ -##-@@@###%-=@%############*##+%#####
:#=*@@#*=+=%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@ :+%@@@* : @@@#*###################+%#####
@@###+*#*#@%##*#+%@*%###@=++=%@#*#%#*+********##*-:=@+ @@@@#: +@ *@@@#############**######*####
#####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@ @ .-+#%@@@@@@@@@@@@@@ #@@@%#############*#*#####**
####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@% @@ :::::::. #@ @@%###@@ @@@@#########**##********
.#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@ @%:.::::::--:: @@ =@*#=#*@@@@ +@@@#*#*******###*###**
#####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#* @@@@#@@+=+****@@@+ : @@ +@#=:%#@ @@@% @@@%#######**#**+***
.####**%**###**%@@ @%#@@ #%#=##==#*@@ @@@@@ @@@@@@@+==+*#@@@@@=: :#@@@ @@ =@#=-###@ #@@@@ @@@@#*************
####*#%*#####+#@@ =@%@ @+@#=+#==#*@* . +@@@@ *@@@*=++==#@@@@@@@: @@:-@#=-*##@= @@#@@@ #@@@#***********
.#######**###**@@= @@@@+ ##@#=+#*=##@ ::. :@@@@@@@- :@*@@@@@@= : -@@=#+==+##*@@: %==@@@@ @@@@#****++++
######*##*##*@@# *@@@= @#@@#=++@+##@ +#= @@@@#+-*%@@@@@@@@@%. %@@@@@@%= @=@#+===##++=%@:@=:#@@@@ -@@@@%#****
#####**##*+*#@% =@%@@.*@@ @%+++=#*@@ . @@@==@@@@@@- .@@@@@+===*+@=## @@@#-+%*@@@: =@@@*++
####***#*+*#@@ :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@# @@@+====@.#@= @@%==#**@@@- :=:::. @@*+
##*+*##*++@@@ #@#@@@ @#@ @@#++=*%@ *@%@@@ . @@#===#=:@@@ @@@%@@@@@@@@= .-: #@*
.##**#****%@@. @@*@@= .@#@ @@@+=++@ @@%@@@ ......:: #@@===@ @@@@ ::#@@= . .:-. @@
#+***++#%@@ @##@@ %@#@ *: @@@+=*@@@@@@ .... . ..::. @@+-*@ @@@. ... . #
*#****##% +@*#@% .: @@#@ :@@@#@@@@ ... .. .:. @@#=#@ - .......
**++##### @##@@: ::: =@#@ .: @@@ ......... . .. .. @%#*@: # : .=**=:.. ..:.
++*####**#**@@ :::: @@@@ @@@: .:.......... ... . . .: -@#+#@ : .:::..:=#%@@@@= .........
+######*+*@@* ::::::: @@@@@@@@ ..:....... ..... . ... . . %+**%@ .. # -** . . ..:...
##**#*+=#@@: ::::::::. . :...:........... . .. .. ##-=#@ . =@@= . ......
####*+#@@* :::-::::: ==-=: .::.:::.. ... .. .... ... ##=-=@ :#+. .::. ...::::
*/
Compilation message (stderr)
election.cpp: In function 'int main()':
election.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |