Farmer John właśnie rozmieścił swoje $N$ bel siana ($1 \leq N \leq 100,000$) w różnych punktach jednowymiarowej drogi przebiegającej przez jego farmę. Aby sprawdzić, czy są odpowiednio oddalone od siebie, pomóż mu odpowiedzieć na $Q$ zapytań ($1 \leq Q \leq 100,000$), z których każde dotyczy liczby bel siana w określonym przedziale drogi.

Wejście

Pierwszy wiersz zawiera $N$ i $Q$.

Następny wiersz zawiera $N$ różnych liczb całkowitych, każdą z zakresu $0 \ldots 1,000,000,000$, wskazujących, że w każdej z tych pozycji znajduje się bela siana.

Każdy z następnych $Q$ wierszy zawiera dwie liczby całkowite $A$ i $B$ ($0 \leq A \leq B \leq 1,000,000,000$), opisujące zapytanie o liczbę bel siana między $A$ i $B$, z uwzględnieniem obu końców.

Wyjście

Wypisz $Q$ wierszy. Dla każdego zapytania wypisz liczbę bel siana w odpowiadającym mu przedziale.

Przykład

Wejście 1

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

Wyjście 1

2
2
3
4
1
0

Autor zadania: Nick Wu