문제

현석이는 충남대학교 캠퍼스의 일직선 도로 위에 $N$개의 물건을 서로 다른 위치에 배치했다. ($1 \le N \le 100\,000$) 현석이는 물건들이 적절한 간격으로 놓여 있는지 확인하기 위해, 특정 구간 안에 포함된 물건의 개수를 묻는 $Q$개의 쿼리에 답하려고 한다. ($1 \le Q \le 100\,000$)

입력

첫째 줄에 물건의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다.

둘째 줄에는 물건이 놓인 위치를 나타내는 $N$개의 서로 다른 정수가 공백으로 구분되어 주어진다. 각 위치는 $0$ 이상 $1\,000\,000\,000$ 이하이다.

다음 $Q$개의 줄에는 각 쿼리를 나타내는 두 정수 $A$와 $B$가 공백으로 구분되어 주어진다. ($0 \le A \le B \le 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