\(N\)개의 정수가 주어진다. 이 정수들은 정렬되어 있지 않으며, 같은 값이 여러 번 등장할 수 있다.

그 뒤에 두 수 \(A\), \(B\)가 주어지는 질문이 \(Q\)개 주어진다. 각 질문마다 주어진 정수들 중에서 \(A\) 이상 \(B\) 이하인 수의 개수를 구하시오.

입력

첫째 줄에 정수의 개수 \(N\)과 질문의 개수 \(Q\)가 공백을 사이에 두고 주어진다.

둘째 줄에 \(N\)개의 정수가 공백으로 구분되어 입력된다.

셋째 줄부터 \(Q\)개의 줄에 걸쳐 각 줄마다 두 정수 \(A\), \(B\)가 공백으로 구분되어 주어진다.

출력

질문이 주어진 순서대로, 각 줄마다 \(A\) 이상 \(B\) 이하인 수의 개수를 출력한다.

제한 사항

• \(1 \le N \le 100000\)
• \(1 \le Q \le 100000\)
• 배열의 원소와 질문으로 주어지는 수는 \(-1000000000\) 이상 \(1000000000\) 이하의 정수이다.
• 각 질문에서 항상 \(A \le B\)이다.
• 배열은 정렬되어 있지 않을 수 있다.
• 같은 값이 여러 번 등장할 수 있다.

예제 입력 1

8 4
7 2 15 1 11 3 9 5
1 5
6 10
11 15
4 4

예제 출력 1

4
2
2
0

예제 입력 2

10 5
3 3 -1 7 0 3 10 -1 5 7
-1 3
3 3
4 7
-10 -2
0 10

예제 출력 2

6
3
3
0
7