L-th K-th number

Time limit2sMemory limit512 MB

Summary

Given N cards, take the K-th smallest value of every contiguous block of length at least K, then report the L-th smallest of all those values.

Level: Hard9 of 10
Topics: Binary search, Array, Prefix sum, Combinatorics
Solved: No attempts yet

Problem

$N$ cards lie in a row. The $i$ -th card from the left ( $1 \le i \le N$ ) has the integer $a_i$ written on it.

You play the following game with these cards. Choose a block of $K$ or more consecutive cards, then do this:

Lay the chosen cards out from the left in increasing order of the integers written on them.
Write down on paper the integer on the $K$ -th card from the left.
Put every chosen card back where it was.

You do this once for every block of $K$ or more consecutive cards. That is, for every pair $(l, r)$ with $1 \le l \le r \le N$ and $K \le r - l + 1$ , you write down the $K$ -th smallest integer among $a_l, a_{l+1}, \dots, a_r$ .

Sort the integers you wrote down in increasing order. The $L$ -th of them, counting from the left, is your score in this game. Find the score.

Input

The input is given from standard input in the following format.

N K L
a_1 a_2 ... a_N

Output

Print the score on a single line.

Constraints

$1 \le N \le 200000$
$1 \le K \le N$
$1 \le a_i \le N$
$1 \le L$
The number of integers written on the paper is at least $L$ .

Examples4

Example 1
Input
```
4 3 2
4 3 1 2
```
Expected output
```
3
```
Example 2
Input
```
5 3 3
1 5 2 2 4
```
Expected output
```
4
```
Example 3
Input
```
6 2 9
1 5 3 4 2 4
```
Expected output
```
4
```
Example 4
Input
```
6 2 8
1 5 3 4 2 4
```
Expected output
```
3
```