Page not loading? Try clicking here.
Placeholder

#7060

영향력 2.5s 1024MB

Problems

길이 N의 수열이 있다.

이 수열의 어느 구간에 대해, 이 구간의 영향력은 다음 조건을 만족하는 x의 최댓값으로 정의한다.

"구간에 속하는 x 이상인 수의 개수가 x개 이상이다."

Q개의 구간에 대해 각 구간의 영향력을 구하시오.


Input

첫 줄에 수열의 길이 N과 쿼리의 개수 Q가 주어진다. (1\leq N, Q\leq 200000)

그 다음 줄에 길이 N의 수열이 주어진다. 각 값은 1 이상 200000이다.

그 다음 줄부터 Q개의 줄에 걸쳐 영향력의 크기를 구할 구간이 주어진다.


Output

각 구간에 대해 그 구간의 영향력의 크기를 한 줄에 하나씩 Q개의 줄에 걸쳐 출력하시오.


Subtask

# Score Condition
#120

N, Q\leq 1000

#255

N, Q\leq 50000

#325

제한 없음


Example 

7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
1
3
3
1
2
2

Source

COCI 2020/2021 Contest #6

You must sign in to write code.