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