h-index
시간 제한2.5초메모리 제한512 MB
인용 횟수 배열에서 각 구간 질의마다 그 구간에 h 이상인 값이 h개 이상 존재하도록 하는 가장 큰 h를 구한다.
문제
h-index는 과학자나 학자의 논문 생산성과 인용 영향을 함께 측정하는 지표이다. 어떤 저자가 인용 횟수가 각각 h 이상인 논문을 h편 발표했다고 할 때, 이러한 h의 최댓값으로 정의된다.
Mirko는 은퇴를 앞두고 있다. 그는 살아생전 n편의 논문을 발표했는데, 이제 q번 다음과 같은 질문을 스스로에게 한다. "내가 li번째부터 ri번째 논문만 발표했다면 내 h-index는 얼마였을까?"
그가 답을 계산하도록 도와주자.
입력
첫째 줄에 정수 n과 q가 주어진다 (1 ≤ n, q ≤ 200 000). n은 논문의 수, q는 질문의 수이다.
둘째 줄에 n개의 정수 pi가 주어진다 (1 ≤ pi ≤ 200 000). pi는 i번째 논문의 인용 횟수이다.
다음 q개의 줄에는 각각 두 정수 li와 ri가 주어진다 (1 ≤ li ≤ ri ≤ n). 이는 i번째 질문의 양 끝점이다.
출력
q개의 줄을 출력한다. i번째 줄에는 i번째 질문의 답을 출력한다.