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

Poveste şi cerinţă...

Fiindca l-a prins jucandu-se pe telefon in timpul orei de Potiuni, profesorul Snape i-a dat lui Harry o tema suplimentara pentru ziua urmatoare. Fiind dat un sir $A$ cu $N$ numere naturale reprezentand codurile vrajilor efectuate de elevii de la Hogwarts in ultimele $24$ de ore, Harry trebuie sa raspunda la $M$ intrebari de genul : "Cate vraji distincte ce au codurile in intervalul $[X,Y]$ au fost efectuate in ultima zi?". Fiind prea ocupat cu Ginny, el va roaga sa ii faceti un program care sa il ajute sa raspunda la toate intrebarile profesorului Snape.

h2. Date de intrare

Fişierul de intrare $distincte2.in$ va contine pe prima linie numerele naturale $N$ si $M$ reprezentand numarul de elemente din sir si respectiv numarul de query-uri. A $2$-a linie a fisierului de intrare contine cele $N$ elemente ale sirului. Urmatoarele $M$ linii vor contine cate $2$ numere $X$ si $Y$ cu $(X ≤ Y)$ reprezentand inceputul si sfarsitul unui interval interogat.

Fişierul de intrare $distincte2.in$ va contine pe prima linie numerele naturale $N$ si $M$ reprezentand numarul de elemente din sir si respectiv numarul de intrebari. A $2$-a linie a fisierului de intrare contine cele $N$ elemente ale sirului. Urmatoarele $M$ linii vor contine cate $2$ numere $X$ si $Y$ $(X ≤ Y)$ reprezentand inceputul si sfarsitul unui interval interogat.

h2. Date de ieşire

Fişierul de ieşire $distincte2.out$ va avea $M$ linii. Pe linia $i$ se va afla un singur numar natural semnificand raspunsul pentru al $i$-lea query.

Fişierul de ieşire $distincte2.out$ va avea $M$ linii. Pe linia $i$ se va afla un singur numar natural semnificand raspunsul pentru a $i$-a intrebare.

h2. Restricţii

* $1 ≤ A[i] ≤ 1 000 000$
* $1 ≤ X ≤ Y ≤ 1 000 000$ pentru fiecare query

h2. Exemplu
table(example). |_. distincte2.in |_. distincte2.out |

  6
|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="distincte2") ==

7803