페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7060

영향력 2.5s 1024MB

문제

길이 N의 수열이 있다.

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

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

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


입력

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

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

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


출력

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


부분문제

번호 점수 조건
#120점

N, Q\leq 1000

#255점

N, Q\leq 50000

#325점

제한 없음


예제 

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

출처

COCI 2020/2021 Contest #6
로그인해야 코드를 작성할 수 있어요.