Sinulla on taulukko, jossa on n kokonaislukua. Lisäksi sinulle annetaan q väliä taulukossa.

Tehtäväsi on selvittää jokaisesta välistä, montako eri lukua välillä on.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut n ja q: taulukon koko ja välien määrä. Taulukon alkiot on numeroitu 1,2,\dots,n.

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

Lopuksi syötteessä on q riviä, joista jokaisella on kaksi kokonaislukua a ja b: kysely kohdistuu väliin [a,b].

Tuloste

Tulosta jokaiseen kyselyyn, montako eri lukua välillä on.

Rajat

• 1 \le n,q \le 2 \cdot 10^5
• 1 \le x_i \le 10^9
• 1 \le a \le b \le n

Esimerkki

Syöte:

5 3
3 2 3 1 2
1 3
2 4
1 5

Tuloste:

2
3
3