← 返回题目列表

AtCoder · scpc2026_div3_c

C. 第K个最小的数字

中文机器翻译题面 查看原题

表示言語

/ /

分数: 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