Se da un sir de n numere naturale (nu neaparat ordonat) si T intrebari. Fiecare intrebare este un interval inchis [x, y]: cate numere din sir au valoarea cuprinsa intre x si y, inclusiv capetele?
- Date de intrare
- Pe prima linie se afla n si T. Pe a doua linie se afla cele n numere ale sirului. Pe fiecare dintre urmatoarele T linii se afla doua numere x si y, cu x <= y.
- Date de iesire
- Se afiseaza T linii; linia k contine raspunsul la a k-a intrebare.
- Restrictii
- 1 <= n, T <= 200 000 0 <= a_i <= 2 000 000 000 0 <= x <= y <= 2 000 000 000
Exemple
Exemplul 1
Intrare
8 6 7 2 9 4 4 12 0 7 3 8 0 0 13 100 4 4 0 2000000000 5 6
Iesire
4 1 0 2 8 0
Exemplul 2
Intrare
3 3 5 5 5 5 5 0 4 6 6
Iesire
3 0 0