election

Election

== include(page="template/taskheader" task_id="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").

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:

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ă mai puţine).

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

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$

* 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