Fişierul intrare/ieşire:memorie.in, memorie.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

memorie.inmemorie.outExplicaţie
8 4
7 43 7 21 35 7 7 7
2 7
3 5
6 8
2 2
4
3
1
1
Intervalul [43 7 21 35 7 7] conţine numerele distincte 43, 7, 21, 35.
Intervalul [7 21 35] conţine numerele distincte 7, 21, 35
Intervalul [7 7 7] conţine doar numărul distinct 7.
Intervalul [43] conţine un singur număr, 43.
Trebuie sa te autentifici pentru a trimite solutii. Click aici