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

#7088

K번째 수 1초 1024MB

문제

배열 a[1...n]에는 서로 다른 수가 n개 저장되어 있다. 우리의 목적은 Q(i,j,k)라는 함수를 구현하는 것이다.

  • Q(i,j,k): 배열 a[i...j]를 정렬했을 때, k번째 수를 리턴하는 함수

예를 들어, a = (1,5,2,6,3,7,4)인 경우 Q(2,5,3)의 답을 구하는 과정을 살펴보자.

a[2...5]는 (5,2,6,3)이고, 이 배열을 정렬하면 (2,3,5,6)이 된다. 정렬한 배열에서 3번째 수는 5이다. 따라서 Q(2,5,3)의 리턴 값은 5이다.

배열 a가 주어지고, Q함수를 호출한 횟수가 주어졌을 때, 각 함수의 리턴 값을 출력하는 프로그램을 작성하시오.


입력

첫째 줄에 배열의 크기 n과 함수 Q를 호출한 횟수 m이 주어진다. (1 ≤ n ≤ 500,000, 1 ≤ m ≤ 5,000)

둘째 줄에는 배열에 포함된 정수가 순서대로 주어진다. 각 정수는 절댓값이 10^9를 넘지 않는 정수이다.

다음 m개 줄에는 Q(i,j,k)를 호출할 때 사용한 인자 i,j,k가 주어진다. (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j-i+1)


출력

Q함수를 호출할 때마다 그 함수의 리턴값을 한 줄에 하나씩 출력한다.


부분문제

번호 점수 조건
#180점

1 ≤ n ≤ 100,000

#220점

예제1

입력
73
1526374
253
441
173
출력
5
6
3

출처

NEERC Northern Subregional 2004 K번

역링크