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

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.

Poveste şi cerinţă...

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

Fişierul de intrare $distincte2.in$ ...

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 a $i$-a intrebare.

În fişierul de ieşire $distincte2.out$ ...

h2. Restricţii

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

* $... ≤ ... ≤ ...$

h2. Exemplu

  6
|

h3. Explicaţie
 
...
 

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

7803