Toata comisia este de acord ca in fiecare an e nevoie de o problema $100%$ clasica. Tu nici nu mai tii minte ce parere ai despre asta. Cert e ca ti s-a dat sa faci testele pentru urmatoarea problema:

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

<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 memmoizeaza 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

h2. Restricţii

* $1 ≤ T ≤ 10$

* $1 ≤ N, M ≤ 10^5^$

* $1 ≤ valorile din sir ≤ 10^9^$

h2. Exemplu

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
|