表示言語
/ /分数: 100 点
问题陈述
无限序列 (a_n) 满足以下属性。
- 对于每个正整数 i 满意 i>N, a_i 等于 K- 第一个元素 a_{i-N},a_{i-N+1},\dots,a_{i-1} 这些值按非降序排序后。
一旦值 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
输出
输出答案。
示例输入 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-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