问题描述

有N张卡片排成一行。第i张卡片（$1 \leq i \leq N$）上写着整数 $a_i$。

JOI要用这些卡片玩以下游戏。选择连续的至少K张卡片，并进行以下操作：

• 按照写着的整数从小到大的顺序将选定的卡片从左至右排列。
• 在排列好的卡片中，将第K张卡片上的整数写在纸上。
• 将选定的卡片全部放回原位。

对于所有连续的至少K张卡片的列都进行这个操作。即，对于满足 $1 \leq l \leq r \leq N$ 和 $K \leq r - l + 1$ 的所有$(l,r)$，将 $a_l, a_{l+1}, ..., a_r$ 中第K小的整数写下来。

按从小到大的顺序排列这些整数。其中，从左边数第L个整数是JOI在这个游戏中的得分。求JOI的得分。

约束条件

• $1 \leq N \leq 200000$
• $1 \leq K \leq N$
• $1 \leq a_i \leq N$
• $1 \leq L$
• JOI所写的整数至少有L个。

---

输入

输入以以下形式从标准输入给出。

$N$ $K$ $L$ $a_1$ $a_2$ $...$ $a_N$

输出

在一行中输出JOI的得分。

子任务1 [6分]

• $N \leq 100$

子任务2 [33分]

• $N \leq 4000$

子任务3 [61分]

• 没有额外的限制。

---

输入样例1

4 3 2
4 3 1 2

输出样例1

3

满足 $1 \leq l \leq r \leq N (= 4)$ 和 $K (= 3) \leq r - l + 1$ 的$(l,r)$共有3种：$(1,3), (1,4), (2,4)$。

对于这些$(l,r)$，$a_l, a_{l+1}, ..., a_r$中第3小的整数分别是4, 3, 3。

其中第2小的整数是3，因此JOI的得分为3。注意，当存在多个相同的整数时，要重复计数。

---

输入样例2

5 3 3
1 5 2 2 4

输出样例2

4

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

其中第3小的整数是4。

---

输入样例3

6 2 9
1 5 3 4 2 4

输出样例3

4

---

输入样例4

6 2 8
1 5 3 4 2 4

输出样例4

3