Farmer John은 농장을 가로지르는 일차원 도로의 여러 위치에 $N$개의 건초 더미 ($1 \leq N \leq 100,000$)를 놓았다. 더미 사이의 간격이 적절한지 확인하기 위해 $Q$개의 질의 ($1 \leq Q \leq 100,000$)에 답하는 것을 도와주자. 각 질의는 도로의 특정 구간 안에 있는 건초 더미의 개수를 묻는다.

입력

첫 번째 줄에는 $N$과 $Q$가 주어진다.

다음 줄에는 각각 $0 \ldots 1,000,000,000$ 범위에 있는 서로 다른 $N$개의 정수가 주어지며, 각 위치에 건초 더미가 하나씩 있음을 나타낸다.

다음 $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