Fișierul intrare/ieșire	memorie.in, memorie.out	Sursă	ad-hoc
Autor	clasică	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.12 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Memorie

În junglă, elefantul se laudă cu memoria lui de... elefant. Iepurașul îi propune un joc ca să-l testeze. Jocul folosește un pachet standard de cărți de joc. De N ori, ei extrag câte o carte. În secret, iepurașul își notează cartea. Apoi reintroduc cartea în pachet și amestecă pachetul. La final, iepurașul îi pune elefantului Q întrebări de forma: între extragerile x și y inclusiv, câte cărți distincte au apărut?

Elefantul, de fapt, este cam senil, așa că vă roagă să îl ajutați.

Date de intrare

Fișierul de intrare memorie.in conține pe prima linie numerele N și Q. Pe a doua linie apar cele N cărți extrase, separate prin spații. Pe următoarele Q linii apare câte o întrebare sub forma unei perechi de numere, x y.

Date de ieșire

În fișierul de ieșire memorie.out se vor afișa răspunsurile la întrebări, câte unul pe linie.

Restricții

• 1 ≤ N ≤ 100.000
• 1 ≤ Q ≤ 200.000
• 1 ≤ x ≤ y ≤ N
• Pentru simplitate, cărțile sunt codificate prin numere de la 1 la 52.

Exemplu