<Vi se da un sir de $N$ numere si $M$ query-uri de forma "care este valoarea maxima din subsecventa $[x, y]?$". Raspundeti la query-uri cu un RMQ.>

Munca in pentru pregatirea acestei probleme a fost paralelizata in urmatorul fel: o persoana construieste secventa de numere. O alta persoana decide numarul de query-uri si raspunsurile acestora. Iar tu alegi efectiv query-urile pentru care se obtin aceste raspunsuri. Inteligent, nu?

Munca pentru pregatirea acestei probleme a fost paralelizata (more like paralizata, am I right?) in urmatorul fel: o persoana construieste secventa de numere. O alta persoana decide numarul de query-uri si raspunsurile acestora. Iar tu alegi efectiv query-urile pentru care se obtin aceste raspunsuri. Inteligent, nu?

Fiindca nu vrei sa intre cele mai nefericite bruturi, iti doresti ca suma lungimilor query-urilor pe care le propui sa fie maxim posibila. De-asemenea, fiindca exista pe lume oameni care memoizeaza si genul asta de probleme, iti doresti ca toate query-urile sa fie distincte.

Fiindca nu vrei sa intre cele mai nefericite bruturi, iti doresti ca suma lungimilor query-urilor pe care le propui sa fie maxim posibila. De-asemenea, fiindca exista pe lume oameni care memoizeaza si la genul asta de probleme, iti doresti ca toate query-urile sa fie distincte.

h2. Date de intrare

5 3
1 2 5 2 1
5 5 5

3 3

3 4

5 3 2

5 5 5

5 5 5 5

| 13
-1
|