== include(page="template/taskheader" task_id="aliniere") ==

Se da un vector cu N elemente si Q impartiri ale acestuia in secvente (nu neaparat disjuncte).
Pentru fiecare impartire data se cere sa se afiseze numarul minim de secvente ce trebuie eliminate astfel incat cele ramase sa poata fi reordonate pentru a obtine un vector sortat crescator.

Doru, profesor de sport, are acum ora cu o clasa de a 9a. Fiind boboci, acestia au o prezenta destul de ridicata, mai exact N. Domn professor ii pune pe elevi sa se alinieze crescator dupa inaltime, insa observa ca acestia s-au aranjat intr-o linie dupa grupurile de prietenii formate. **Elevii nu vor in niciun fel sa isi paraseasca grupul si nici sa schimbe ordinea din interiorul grupului**. Deoarece vorbeste toata lumea cu toata lumea, Doru, algoritmician in timpul liber, nu isi da seama exact care sunt grupurile asa ca ii numeroteaza pe elevi incepand cu 0 de la stanga la dreapta isi pune Q intrebari de forma:
“Daca grupurile sunt (1, 2, … , x[0]), (x[0]+1, … , x[1]), (x[1]+1, … , x[2]), … , (x[k-1]+1, … , n), care este numarul minim de grupuri pe care trebuie sa il dau afara pentru a putea alinia elevii crescator?”
Ajutati-l pe Doru sa raspunda la intrebare.

h2. Date de intrare

Fişierul de intrare $aliniere.in$ contine pe prima linie numarul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând vectorul. Pe a treia linie se afla numarul natural Q. Pe fiecare linie i din urmatoarele Q se afla un numar natural K[i] ce reprezinta numarul de secvente din impartirea i, iar apoi K[i] perechi de numere reprezentand capetele secventelor.

Fişierul de intrare aliniere.in contine pe prima linie numarul natural N. Pe a doua linie se află N numere naturale, separate prin câte un spaţiu, reprezentând inaltimile elevilor. Pe a treia linie se afla numarul natural Q. Pe fiecare linie i din urmatoarele Q se afla un numar natural K[i] ce reprezinta numarul de grupuri din intrebarea i, iar apoi K[i] numere ce reprezinta vectorul x.

h2. Date de ieşire

Fişierul de ieşire $aliniere.out$ va contine Q numere, al i-ulea numar reprezentand numarul minim de secvente eliminate din impartirea i.

Fişierul de ieşire aliniere.out va contine Q numere, al i-ulea numar reprezentand raspunsul pentru intrebarea numarul i.

h2. Restricţii

* 1 ≤ N ≤ 100 000
* 1 ≤ Q ≤ 1000
* 1 ≤ K[i] ≤ 1000, oricare ar fi 1 ≤ i ≤ Q
* 1 ≤ v[i] ≤ $10^9^$, oricare ar fi 1 ≤ i ≤ N
* pentru 30 de puncte: 1 ≤ N, K[i], Q ≤ 12, oricare ar fi 1 ≤ i ≤ Q
 
* elementele vectorului si implicit capetele secventelor sunt **indexate de la 0**

* 1 ≤ N ≤ 100 000
* 1 ≤ Q ≤ 1000
* 1 ≤ K[i] ≤ 1000, oricare ar fi 1 ≤ i ≤ Q
* Toti cei Q vectori “x” sunt sortati strict crescator si au elementele < N
* 1 ≤ inaltime elev ≤ 109
* pentru 30 de puncte: 1 ≤ N, K[i], Q ≤ 12, oricare ar fi 1 ≤ i ≤ Q

h2. Exemplu