건초 더미 개수 세기

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

보통4정렬이분 탐색배열누적 합면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제5

문제

농부 존이 농장을 가로지르는 일차원 도로 위 여러 지점에 건초 더미 $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$ 개의 줄을 출력한다. 각 질의마다 입력 순서대로 그 구간에 있는 건초 더미의 개수를 한 줄에 출력한다.