== include(page="template/taskheader" task_id="election") ==

Poveste şi cerinţă...

Astăzi trebuie să decidem care este cea mai bună echipă de supereroi: Echipa Căpitanului, sau Echipa Iron Man (Tony) ?
Sunt $N$ fani nervoşi, iar fiecare dintre ei trebuie să voteze pentru echipa lui preferată de supereroi: fie $C$ ("Căpitanul"), sau $T$ ("Tony").
Cum Căpitanul ştie că nu are nicio şansă de câştig, şi cum este un om cinstit, decide să fraudeze alegerile. El vrea să anuleze un număr minim de voturi.
Votarea se face de două ori:

h2. Date de intrare
 
Fişierul de intrare $election.in$ ...

* în ordinea crescătoare a indicilor fanilor (mai puţin cei cu un vot nulificat).
* în ordinea descrescătoare a indicilor fanilor (mai puţin cei cu un vot nulificat).

h2. Date de ieşire

Căpitanul este fericit dacă la fiecare moment în timpul numărării voturilor el NU pierde lui Tony (nu are nevoie să aibă mai multe voturi, ci doar să nu aibă mai puţine).
Desigur, nimeni nu se poate lua de Tony. El ştie planul Căpitanului, şi ar vrea să ştie pentru $Q$ scenarii care este numărul de voturi pe care Căpitanul le va anula. Un scenariu este definit de două numere $L$ şi $R$, ce semnfică că doar fanii cu indicii de la $L$ la $R$ inclusiv au să participe la sesiunea de votare

În fişierul de ieşire $election.out$ ...

h2. Date de intrare

h2. Restricţii

Prima linie a fişierului de intrare $election.in$ conţine un singur număr $N$, numărul de fani.
A doua linie conţine un şir de $N$ caractere din mulţimea ${C, T}$, voturile fiecărui fan.
A treia linie conţine un singur număr $Q$, numărul de scenarii.
Următoarele $Q$ linii descriu cele $Q$ scenarii în forma $L R$ ($1 ≤ L ≤ R ≤ N$).

* $... ≤ ... ≤ ...$

h2. Date de ieşire
Fişierul de ieşire $election.out$ conţine $Q$ linii. A $i$-a linie va conţine rezultatul pentru cel de-al $i$-leq scenariu.

h2. Exemplu

h2.  Restricţii și precizări

table(example). |_. election.in |_. election.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

* Pentru 28 puncte, $1 ≤ N, Q ≤ 2.000$
* Pentru alte 54 puncte, $1 ≤ N, Q ≤ 70.000$
* Pentru alte 18 puncte, $1 ≤ N, Q ≤ 500.000$
 
h2. Exemple
 
table(example). |_. tricolor.in |_. tricolor.out |
|
11
CCCTTTTTTCC
3
1 11
4 9
1 6
|4
6
3

|

h3. Explicaţie
 
...

h2. Explicatie

== include(page="template/taskfooter" task_id="election") ==

În primul scenariu, voturile arată aşa: "CCCTTTTTTCC". Singura soluţie e să se anuleze 4 dintre voturile pentru Tony.
În cel de al doilea scenariu, voturile arată aşa: "TTTTTT". Singura soluţie e să se anuleze toate voturile.
În ultimul scenariu, voturile arată aşa: "CCCTTT". Singura soluţie e să se anuleze toate voturile lui Tony.