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 (0, 1, … , x ~0~ ), (x ~0~ +1, … , x ~1~ ), (x ~1~ +1, … , x ~2~ ), … , (x ~k-1~ +1, … , n-1), 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.

Ajutati-l pe Doru sa raspunda la intrebari.

h2. Date de intrare