AT_scpc2026_div2_f.The Kth Smallest Number

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$.

一个无限序列 $(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$。

The input is given from Standard Input in the following format:

$N$ $K$ $M$
$a_1$ $a_2$ $\dots$ $a_N$

输入从标准输入中按以下格式给出：

$N$ $K$ $M$
$a_1$ $a_2$ $\dots$ $a_N$

Output the answer.

输出答案。

表示言語

/ /

Sample 1 Explanation:
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 2 Explanation:

---

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.

表示语言

/ /

样例 1 解释：
将 $[2,0,2,6,0,5,1,6]$ 按非递减顺序排序，得到 $[0,0,1,2,2,5,6,6]$。由于 $K=6$，故 $a_9=5$。

样例 2 解释：

---

约束条件

• $1 \leq K \leq N \leq 300\,000$
• $1 \leq M \leq 10^{18}$
• $-10^9 \leq a_i \leq 10^9$
• 所有输入值均为整数。