CSES - Eri luvut
  • Time limit: 1.00 s
  • Memory limit: 128 MB
Annettuna on taulukko, jossa on $n$ lukua, sekä $m$ kyselyä taulukkoon.

Jokaisessa kyselyssä annettuna on väli $a \ldots b$ ja tehtäväsi on selvittää, montako eri lukua taulukossa on kyseisellä välillä.

Syöte

Syötteessä on ensin kaksi kokonaislukua $n$ ja $m$: taulukon koko ja kyselyiden määrä.

Seuraavalla rivillä on $n$ kokonaislukua $x_1,x_2,\ldots,x_n$: taulukon sisältö.

Lopuksi syötteessä on $m$ riviä, joista jokainen kuvaa yhden kyselyn. Rivillä on kokonaisluvut $a$ ja $b$.

Tuloste

Tulosta jokaiseen kyselyyn eri lukujen määrä välillä $a \ldots b$.

Rajat
  • $1 \le n, m \le 10^5$
  • $1 \le x_i \le 10^6$
  • $1 \le a \le b \le n$
Esimerkki

Syöte:
8 3
2 3 1 2 2 3 4 1
2 6
3 5
1 8


Tuloste:
3
2
4