In the first line, the number of input keys N (1 ≤ N ≤ 100000) and the range of input keys M (1 ≤ M ≤ 100000) and number of query ranges K (1 ≤ K ≤ 100000) are given. In the next K lines, two numbers A[i] and B[i] are given. (1 ≤ i ≤ K) In the next N lines, a key is given in each line.


문제가 뭐냐면요.


첫째줄에 양수 N과 M, K를 입력하고


K라인에 걸쳐서 양수 A[i], B[i]를 입력.


그 다음 N개의 양수를 입력.



그리고 각각 A[i]<=N<=B[i]가 성립하는 N개의 개수를 K라인에 걸쳐서 출력하는 문제입니다.



입력예시는 다음과 같고요.

5 100 3 

20 60 

30 70 

10 50 

10 

50 

40 

20 

80


출력예시는 다음과 같습니다.

3

2

4


시간 제한만 없다면 간단한 문제인데


시간 제한 때문에 계속 막히네요.


이중 포문 말고는 도저히 방법이 생각이 안나요.


알고리즘을 어떻게 짜야하는지 빡대가리라서 웁니다..



지금 제가 한 방법 중에서 가장 빠른 애는


입력된 N개의 양수를 정렬해서


아래부터 제일 작은 값과 제일 큰 값을 각각 A[i]와 B[i] 비교하는 식으로 짰거든요.


그래서 제일 작은 값은 비교 후 증가 큰 값을 비교 후 감소로 해서 저 범위 내에 들어가는 제일 작은 값과 큰 값 사이의 값들은 굳이 볼 필요가 없기 때문에


넘어가는 식으로요. 그런데도 이중 포문을 사용해서 그런지 시간이 그렇게 감소하지가 않네요...


동적계획법 공부하고 있는데 도저히 모르겟어요.