頁面無法載入？點擊這裡可能會修復。
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

需要登入才能撰寫程式碼。