AT_joi2018_yo_f.L番目のK番目の数 (LthKthNumber)

有 $N$ 张卡片排成一排。从左至右，第 $i$ 张卡片（$1 \le i \le N$）上标有整数 $a_i$。

JOI 君要进行一个游戏，他需要在这些卡片中选择一段连续的、至少 $K$ 张的卡片子序列，并进行以下操作：

1. 按从小到大的顺序对所选卡片上的数字进行排序。
2. 记录排序后从左数的第 $K$ 张卡片上的数字。
3. 把这些卡片复位到原来的位置。

JOI 君会对所有满足条件的 $(l, r)$（其中 $1 \le l \le r \le N$ 且 $K \le r - l + 1$）执行这一操作。对于每一个这样的 $(l, r)$，他都会记录 $a_l, a_{l+1}, \ldots, a_r$ 中的第 $K$ 小的数。

最后，将所有记录的数从小到大排序，JOI 君的得分就是排在第 $L$ 位的数字。请计算 JOI 君的得分。

从标准输入读取以下格式的内容：

$N$ $K$ $L$ $a_1$ $a_2$ $\ldots$ $a_N$

输出一行，表示 JOI 君的得分。

约束条件

• $1 \le N \le 200000$
• $1 \le K \le N$
• $1 \le a_i \le N$
• $1 \le L$
• JOI 君所记录的整数数达到或超过 $L$ 个。

子任务 1 [6 分]

• $N \le 100$

子任务 2 [33 分]

• $N \le 4000$

子任务 3 [61 分]

• 无附加限制。

样例说明 1

对于 $1 \le l \le r \le N (= 4)$ 且 $K (= 3) \le r - l + 1$，符合条件的 $(l, r)$ 有 $(1, 3), (1, 4), (2, 4)$ 三种组合。对于这些组合，$a_l, a_{l+1}, \ldots, a_r$ 中第 3 小的数分别是 $4, 3, 3$。排序后，第 $L (= 2)$ 小的数是 $3$，所以 JOI 君的得分是 $3$。需要注意，相同的数要重复计数。

样例说明 2

JOI 君记录的数如下：

• 对 $(l, r) = (1, 3)$ 他记录 $5$
• 对 $(l, r) = (1, 4)$ 他记录 $2$
• 对 $(l, r) = (1, 5)$ 他记录 $2$
• 对 $(l, r) = (2, 4)$ 他记录 $5$
• 对 $(l, r) = (2, 5)$ 他记录 $4$
• 对 $(l, r) = (3, 5)$ 他记录 $4$

在这些数中，由小到大排序后，第 $L (= 3)$ 小的数是 $4$。

本翻译由 AI 自动生成