L-th K-th number

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.

Hard9Binary searchArrayPrefix sumCombinatoricsNo attempts yetTime limit2sMemory limit512 MB

Problem

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

You play the following game with these cards. Choose a block of KK 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 KK-th card from the left.
  • Put every chosen card back where it was.

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

Sort the integers you wrote down in increasing order. The LL-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

  • 1N2000001 \le N \le 200000
  • 1KN1 \le K \le N
  • 1aiN1 \le a_i \le N
  • 1L1 \le L
  • The number of integers written on the paper is at least LL.