/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
An infinite sequence (a_n) satisfies the following property.
- For every positive integer i satisfying i>N, a_i is equal to the K-th element of a_{i-N},a_{i-N+1},\dots,a_{i-1} after these values are sorted in nondecreasing order.
Once the values of a_1,\dots,a_N are determined, the values of a_{N+1},a_{N+2},\dots are uniquely determined.
You are given the values of N, K, M and a_1,\dots,a_N. Find a_M.
Constraints
- 1 \leq K \leq N \leq 300\,000
- 1 \leq M \leq 10^{18}
- -10^9 \leq a_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K M a_1 a_2 \dots a_N
Output
Output the answer.
Sample Input 1
8 6 9 2 0 2 6 0 5 1 6
Sample Output 1
5
Sorting [2,0,2,6,0,5,1,6] in nondecreasing order, we have [0,0,1,2,2,5,6,6]. Since K=6, we have a_9=5.
Sample Input 2
1 1 1 1
Sample Output 2
1
表示言語
/ /점수 : 100 점
문제
수열 (a_n)은 다음 성질을 만족하는 무한 수열이다.
- i>N을 만족하는 모든 양의 정수 i에 대하여 a_{i-N},a_{i-N+1},\dots,a_{i-1}을 오름차순으로 정렬할 때 K번째에 오는 수가 a_i와 같다.
a_1,\dots,a_N의 값이 결정되면 a_{N+1},a_{N+2},\dots의 값은 유일하게 결정된다.
N, K, M과 a_1,\dots, a_N의 값이 주어질 때 a_M의 값을 구해 보자.
제한
- 1 \leq K \leq N \leq 300\,000
- 1 \leq M \leq 10^{18}
- -10^9 \leq a_i \leq 10^9
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N K M a_1 a_2 \dots a_N
출력
a_M을 출력한다.
입력 예 1
8 6 9 2 0 2 6 0 5 1 6
출력 예 1
5
[2,0,2,6,0,5,1,6]을 오름차순으로 나열하면 [0,0,1,2,2,5,6,6]이고 K=6이므로 a_9=5이다.
입력 예 2
1 1 1 1
출력 예 2
1
表示言語
/ /配点 : 100 点
問題文
無限数列 (a_n) は次の性質を満たします．
- i>N を満たすすべての正整数 i に対し，a_i は a_{i-N},a_{i-N+1},\dots,a_{i-1} を昇順に並べたときの K 番目の数に等しい．
a_1,\dots,a_N の値が決まると，a_{N+1},a_{N+2},\dots の値は一意に決まります．
N, K, M と a_1,\dots,a_N の値が与えられます．a_M の値を求めてください．
制約
- 1 \leq K \leq N \leq 300\,000
- 1 \leq M \leq 10^{18}
- -10^9 \leq a_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N K M a_1 a_2 \dots a_N
出力
a_M を出力せよ．
入力例 1
8 6 9 2 0 2 6 0 5 1 6
出力例 1
5
[2,0,2,6,0,5,1,6] を昇順に並べると [0,0,1,2,2,5,6,6] になります．K=6 なので，a_9=5 です．
入力例 2
1 1 1 1
出力例 2
1