만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

건초 더미 개수 세기

면접 대비

시간 제한2초메모리 제한512 MB

요약
서로 다른 N개의 건초더미 위치와 Q개의 구간 질의가 주어질 때, 각 폐구간 [A, B] 안에 들어가는 위치의 개수를 구한다.
난이도

보통10점 중 4점

유형
정렬, 이분 탐색, 배열, 누적 합
정답자
아직 제출이 없습니다

문제

농부 존이 농장을 가로지르는 일차원 도로 위 여러 지점에 건초 더미 NN개를 놓았다 (1≤N≤100 0001 \le N \le 100\,000). 간격이 적당한지 확인하려고 질의 QQ개에 답해야 한다 (1≤Q≤100 0001 \le Q \le 100\,000). 각 질의는 도로의 특정 구간에 놓인 건초 더미의 개수를 묻는다.

입력

첫째 줄에 NN과 QQ가 주어진다.

둘째 줄에 서로 다른 정수 NN개가 주어진다. 각 정수는 00 이상 1 000 000 0001\,000\,000\,000 이하이고, 그 위치에 건초 더미가 하나 있다는 뜻이다.

이어지는 QQ개의 줄에 정수 AA와 BB가 주어진다 (0≤A≤B≤1 000 000 0000 \le A \le B \le 1\,000\,000\,000). 위치가 AA 이상 BB 이하인 건초 더미의 개수를 묻는 질의다.

출력

QQ개의 줄을 출력한다. 각 질의마다 입력 순서대로 그 구간에 있는 건초 더미의 개수를 한 줄에 출력한다.

예제5

  1. 예제 1

    입력
    4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10
    예상 출력
    2
2
3
4
1
0

  2. 예제 2

    입력
    1 1
0
0 0
    예상 출력
    1

  3. 예제 3

    입력
    1 3
1000000000
0 999999999
1000000000 1000000000
0 1000000000
    예상 출력
    0
1
1

  4. 예제 4

    입력
    5 8
0 2 4 6 1000000000
0 0
1 1
2 2
3 3
6 6
999999999 999999999
1000000000 1000000000
0 1000000000
    예상 출력
    1
0
1
0
1
0
1
5

  5. 예제 5

    입력
    6 5
10 20 30 40 50 60
0 9
61 1000000000
11 19
10 60
35 45
    예상 출력
    0
0
0
6
1