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 nn ja qq: taulukon lukujen määrä ja kysyttävien välien määrä.

Seuraavalla rivillä on nn kokonaislukua x1,x2,,xnx_1,x_2,\ldots,x_n, jotka kuvaavat taulukon sisällön.

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

Tuloste

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

Rajat

  • 1n1051 \le n \le 10^5
  • 109xi109-10^9 \le x_i \le 10^9
  • 1q1051 \le q \le 10^5
  • 1abn1 \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"