CSES - Välit
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Sinulle on annettu taulukko kokonaislukuja. Lisäksi sinulle on annettu joukko taulukon välejä. Tehtäväsi on selvittää jokaisesta välistä, montako eri lukua siihen kuuluu.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja q: taulukon lukujen määrä ja kysyttävien välien määrä.

Seuraavalla rivillä on n kokonaislukua x_1,x_2,\ldots,x_n, jotka kuvaavat taulukon sisällön.

Lopuksi syötteessä on q riviä, joista jokainen sisältää kaksi kokonaislukua a ja b. Tämä tarkoittaa, että täytyy laskea, montako eri lukua on taulukon välillä [a,b].

Tuloste

Ohjelmasi tulee tulostaa jokaisesta välistä, montako eri lukua siihen kuuluu.

Rajat

  • 1 \le n \le 10^5
  • -10^9 \le x_i \le 10^9
  • 1 \le q \le 10^5
  • 1 \le a \le b \le n

Esimerkki

Syöte:

8 3
2 4 3 2 2 5 3 2
1 8
4 5
6 8

Tuloste:

4
1
3

Vihje: lue "KKKK: Neliöjuurirakenteet"