Farmer John только что разместил $N$ тюков сена ($1 \leq N \leq 100,000$) в различных точках одномерной дороги, проходящей через его ферму. Чтобы убедиться, что расстояния между ними подходящие, помогите ему ответить на $Q$ запросов ($1 \leq Q \leq 100,000$), каждый из которых спрашивает количество тюков сена в заданном интервале дороги.

Входные данные

Первая строка содержит $N$ и $Q$.

Следующая строка содержит $N$ различных целых чисел, каждое в диапазоне $0 \ldots 1,000,000,000$, обозначающих, что в каждой из этих точек находится тюк сена.

Каждая из следующих $Q$ строк содержит два целых числа $A$ и $B$ ($0 \leq A \leq B \leq 1,000,000,000$), задающих запрос на число тюков сена между $A$ и $B$ включительно.

Выходные данные

Выведите $Q$ строк. Для каждого запроса выведите количество тюков сена в соответствующем интервале.

Примеры

Входные данные 1

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

Выходные данные 1

2
2
3
4
1
0

Автор задачи: Nick Wu