using namespace std ;
#include <bits/stdc++.h>
#define TASKNAME "GeneTech"
#define DEBUG(VAL) cerr << #VAL << ": " << VAL << "\n"
const int N = 500000 ;
const int M = 2000000 ;
struct NodeType
{
int sum , min_surf ;
NodeType(int _sum = 0 , int _min_surf = 0) :
sum(_sum) , min_surf(_min_surf) { }
friend NodeType operator+ (NodeType& shl , NodeType& shr)
{
int _sum = shl.sum + shr.sum ;
int _min_surf = min(shl.min_surf + shr.sum , shr.min_surf) ;
return NodeType(_sum , _min_surf) ;
}
} ;
struct QueryType
{
int right , pos ;
QueryType(int _right = 0 , int _pos = 0) :
right(_right) , pos(_pos) { }
} ;
int n , q ;
char gen[N + 1] ;
int a[N] ;
NodeType seg[M] ;
vector < QueryType > queries[N] ;
int answer[N] ;
void Build(int id , int left , int right)
{
if (right - left < 2) seg[id] = NodeType(1 , 0) ;
else
{
int mid = (left + right) >> 1 ;
Build(2 * id + 1 , left , mid) ;
Build(2 * id + 2 , mid , right) ;
seg[id] = seg[2 * id + 1] + seg[2 * id + 2] ;
}
}
void Update(int id , int left , int right , int pos , int value)
{
if (right - left < 2) seg[id] = NodeType(a[left] = value , value) ;
else
{
int mid = (left + right) >> 1 ;
if (pos < mid) Update(2 * id + 1 , left , mid , pos , value) ;
else Update(2 * id + 2 , mid , right , pos , value) ;
seg[id] = seg[2 * id + 1] + seg[2 * id + 2] ;
}
}
NodeType Query(int id , int left , int right , int bound)
{
if (right - bound < 2) return seg[id] ;
int mid = (left + right) >> 1 ;
if (bound < mid) return Query(2 * id + 1 , left , mid , bound) ;
NodeType left_query = Query(2 * id + 1 , left , mid , mid - 1) ;
NodeType right_query = Query(2 * id + 2 , mid , right , bound) ;
return left_query + right_query ;
}
int main()
{
// freopen(TASKNAME".inp" , "r" , stdin) ;
// freopen(TASKNAME".out" , "w" , stdout) ;
ios::sync_with_stdio(false) ;
cout.tie(nullptr) ;
cin.tie(nullptr) ;
cin >> n >> gen ;
for (int i = 0 ; i < n ; ++i)
a[i] = (gen[i] == 'C' ? 1 : -1) ;
cin >> q ;
for (int i = 0 ; i < q ; ++i)
{
int left , right ;
cin >> left >> right ;
queries[--left].emplace_back(--right , i) ;
}
Build(0 , 0 , n) ;
vector < int > my_stack ;
for (int i = n - 1 ; i >= 0 ; --i)
{
if (a[i] < 0) Update(0 , 0 , n , i , 0) , my_stack.push_back(i) ;
else if (my_stack.size())
{
Update(0 , 0 , n , my_stack.back() , -1) ;
my_stack.pop_back() ;
}
for (auto _queries : queries[i])
{
int zero_count = upper_bound(my_stack.rbegin() , my_stack.rend() , _queries.right) - my_stack.rbegin() ;
int negative_count = Query(0 , 0 , n , _queries.right).min_surf ;
answer[_queries.pos] = zero_count - negative_count ;
}
}
for (int i = 0 ; i < q ; ++i)
cout << answer[i] << "\n" ;
return 0 ;
}
