#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#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 = 5e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);
struct node{
int ls , rs , s , ans;
node(){}
node(int ls , int rs , int s , int ans) : ls(ls) , rs(rs) , s(s) , ans(ans){}
};
node st[4 * nd];
char d[nd];
node Merge(node a , node b){
int ls = min(a.ls , a.s + b.ls);
int rs = min(b.rs , b.s + a.rs);
int s = a.s + b.s;
int ans = max({a.ans - b.s , b.ans - a.s , -(a.ls + b.rs)});
return {ls , rs , s , ans};
}
void build(int id , int l , int r){
if(l == r){
if(d[l] == 'C') st[id] = {0 , 0 , 1 , 0};
else st[id] = {-1 , -1 , -1 , 1};
return;
}
int mid = (r + l) / 2;
build(id * 2 , l , mid);
build(id * 2 + 1 , mid + 1 , r);
st[id] = Merge(st[id * 2] , st[id * 2 + 1]);
}
node get(int id , int l , int r , int a , int b){
if(l > b || r < a) return {0 , 0 , 0 , 0};
if(a <= l && r <= b) return st[id];
int mid = (r + l) >> 1;
return Merge(get(id * 2 , l , mid , a , b) , get(id * 2 + 1 , mid + 1 , r , a , b));
}
void solve(){
int n;
cin >> n;
FOR(i , 1 , n) cin >> d[i];
build(1 , 1 , n);
int q;
cin >> q;
while(q --){
int l , r;
cin >> l >> r;
cout << get(1 , 1 , n , l , r).ans << '\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);
}
solve();
return 0;
}
/*
-. ::. -: .::::::::::
***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######:
**##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%%#+########+*@%%@#*##+=@%######:
#%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%%#=+###*##*+#@##@%###+=%%#####:
#####***%##@%+***#%#++#######*********++***#*#+##%%%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%%#+*######*+%%###@###*=#%####:
##*****####@*+***###+=**#+==*+*###%#%%###%%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%%*#*+%%###:
%##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###:
*####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##:
#**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%%*%+*####****@######%%**#%#:
####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%%@@%#####=%%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###.
###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%%*##*#**##**+@#######@**##:
###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##.
###*#%#%%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%%#######@+##:
###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%:
##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@ @@@=-=+##@%=##+#*#***#%###########.
##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%%=******+*****=#@@ @@@*:-#@%+=%+#*###+#@###########:
:@#*#%##%#**##+#%+************#*****++***+#*+-%%@==+++*=+@=++++==@ @@#%=##%==+*++*+*****=#@@ @@@@#*#@*-@+***##+#%########%%#:
#@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%%-==**#@@@@@@##%+#%%-=+++++**+**==@@ @#*+@*=##***##+*@###########:
@*%%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@ @@#####@#=++**+******-@= *@@@@@@@@@@@=+#****#*+@###########:
@@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@ @@######@+=+++++++*++=@ @@@@@@@@ +@@=+#****#*=%%##########:
#@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@ .. @@#####%@-=***+*****=@@@@@@ .@@.@ @#=***#+#*=@@##########:
@%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@ .: @@#####@@=+++++*++**=@@%@@@ -@@@:*@=*#**+#*+@*@#########:
=: ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@ .. #@@#####@#=+**+*+#@@%#@##@@ @ @-=@=****+%*=@-#@%#######:
: :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@ -*+ =@@#####@*=+**++#= -@% : @% -@==@=#***+@*=@% +@@######:
@@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*. *:: -@@*####%#-++++##=:% @-@@% *@=-@=#***+@+=%@@. @@@%###:
+@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@# @@####%%*-=+++#+=@@ : +@+=@+#**++@+=@#%@%- -##%%:
##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@ @@@*##%##===++**#@ .. :@*-@%***+*@==@###%@@%####:
###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@ ::++ =@@***#*#=-==++=@@ @#=#@*+*=#%==@@%#*###%@##.
#*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@ @@@*+%##*--=+==@+ . @@+#@*=+=@#==@###%%%#####.
**@ @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@ @ @@ @@@+*#+**:-==*@ . @@**@+=+*%#=+@###########.
++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@ @@ . . @@@@#=+**=--#@ +@**@+==##*-#@###########:
-@@@ @#-======%%@*===*###@@@@#=----==+==-=#@@@@ @@* :@= @@@@@#*#=:#@ @*#@==+%#+*#@%##########:
%@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@ ::.+@#: :#@@@@#+#@@ @#@@--%%#=#*%###########:
%@@ @%@#%##++======------=========#%@@@@=====*=@#%@@%- ... @@@@@@@@# @*@#:=@#**#*@###########.
@@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@ . . .*% @@@:-@##=#+#@#%#########.
@@@**=@++++=:=%%##@@@##%%%##*+==@%==++******+*#@ .. . # @@*:##**##+#%##########%.
+@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@= . .. =. @@@.:@*#*##+@%###########
:%#**#%@=**+=%%###@@+@#%++******=*@@#=********+%@@ . @@.:@**###*+@###*%#######.
:#+*##@%+**=%%###*@+##@#%*=*#***+=@%@++******+++@@ @@:.@@=#**#=@@############.
++##%@*++=#@###*%@*##@##%#=+****=#%%#=**+*****+%@ @@.=@@@=*##*=@######%######
#%%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+ . @@.#%#@%=###=#%#%####%######
:@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@ @ %@@@##@@++##=-@###%##########
+-=@@=+@%####*%%%%%%###%@*##%%==+=#%#%%+=+*****==@ :=-:: @@@@*#%#@=*#+-@########=@#####
**%@#*%%####*#@%@*%%#%##@#*##%@*==+%###@*=+*++*+-@@ ::: @@%%#@###%+#=.@%########+%#####
#@@########*@@@@%:@%%%###@%####%@+:##@##%*=+*+++==@ :@@%%@####@**-:@%######%*#*######
@%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@ @@ =@@%######@@+ =@%#################
=%#######+@@##@#+*=@##%%####@%##############@=======@ @%@-@@@#######@%: @@##########%#*######
.######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@ :. **@@:@@@#####@# +@%#############*######
.#%##+@@@%=#%@#*#**@#%%####@:=%@##%##*######*##@*=-==#@ :=@@: @ -##-@@@###%-=@%############*##+%#####
:#=*@@#*=+=%%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@ :+%@@@* : @@@#*###################+%#####
@@###+*#*#@%##*#+%%%@*%###@=++=%@#*#%%#*+********##*-:=@+ @@@@#: +@ *@@@#############**######*####
#####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@ @ .-+#%@@@@@@@@@@@@@@ #@@@%#############*#*#####**
####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@% @@ :::::::. #@ @@%###@@ @@@@#########**##********
.#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@ @%:.::::::--:: @@ =@*#=#*@@@@ +@@@#*#*******###*###**
#####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#* @@@@#@@+=+****@@@+ : @@ +@#=:%#@ @@@% @@@%#######**#**+***
.####**%%**###**%@@ @%#@@ #%#=##==#*@@ @@@@@ @@@@@@@+==+*#@@@@@=: :#@@@ @@ =@#=-###@ #@@@@ @@@@#*************
####*#%*#####+#@@ =@%%@ @+@#=+#==#*@* . +@@@@ *@@@*=++==#@@@@@@@: @@:-@#=-*##@= @@#@@@ #@@@#***********
.#######**###**@@= @@@@+ ##@#=+#*=##@ ::. :@@@@@@@- :@*@@@@@@= : -@@=#+==+##*@@: %==@@@@ @@@@#****++++
######*##*##*@@# *@@@= @#@@#=++@+##@ +#= @@@@#+-*%@@@@@@@@@%. %@@@@@@%= @=@#+===##++=%@:@=:#@@@@ -@@@@%#****
#####**##*+*#@% =@%@@.*@@ @%+++=#*@@ . @@@==@@@@@@- .@@@@@+===*+@=## @@@#-+%*@@@: =@@@*++
####***#*+*#@@ :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@# @@@+====@.#@= @@%==#**@@@- :=:::. @@*+
##*+*##*++@@@ #@#@@@ @#@ @@#++=*%@ *@%%@@@ . @@#===#=:@@@ @@@%@@@@@@@@= .-: #@*
.##**#****%@@. @@*@@= .@#@ @@@+=++@ @@%@@@ ......:: #@@===@ @@@@ ::#@@= . .:-. @@
#+***++#%@@ @##@@ %@#@ *: @@@+=*@@@@@@ .... . ..::. @@+-*@ @@@. ... . #
*#****##%% +@*#@% .: @@#@ :@@@#@@@@ ... .. .:. @@#=#@ - .......
**++##### @##@@: ::: =@#@ .: @@@ ......... . .. .. @%#*@: # : .=**=:.. ..:.
++*####**#**@@ :::: @@@@ @@@: .:.......... ... . . .: -@#+#@ : .:::..:=#%@@@@= .........
+######*+*@@* ::::::: @@@@@@@@ ..:....... ..... . ... . . %+**%@ .. # -** . . ..:...
##**#*+=#@@: ::::::::. . :...:........... . .. .. ##-=#@ . =@@= . ......
####*+#@@* :::-::::: ==-=: .::.:::.. ... .. .... ... ##=-=@ :#+. .::. ...::::
*/
