Fişierul intrare/ieşire:	election.in, election.out	Sursă	BOI 2018
Autor	Andrei Constantinescu, Bogdan Ciobanu	Adăugată de	Andrei Constantinescu •Andrei1998
Timp execuţie pe test	1 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Election

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:

• î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).

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

Date de intrare

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, unde 1 ≤ L ≤ R ≤ N.

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.

Restricţii și precizări

• 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

Exemple

Explicatie

Î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.