== 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 *separat*:
* în ordinea crescătoare a indicilor fanilor (mai puţin cei cu votul anulat).
* în ordinea descrescătoare a indicilor fanilor (mai puţin cei cu votul anulat).
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ă strict 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
h2. Date de intrare
Fişierul de intrare $election.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $election.out$ ...
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. Restricţii
h2. 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$
h2. Exemplu
h2. Exemple
table(example). |_. election.in |_. election.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 11
CCCTTTTTTCC
3
1 11
4 9
1 6
| 4
6
3
|
h3. Explicaţie
h2. 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.
== include(page="template/taskfooter" task_id="election") ==
