Time Limit : sec, Memory Limit : KB
Japanese

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

問題文

横一列に並べられた N 枚のカードがある.左から i 枚目(1 ≦ i ≦ N)のカードには,整数 a_i が書かれている.

JOI 君は,これらのカードを用いて次のようなゲームを行う.連続する K 枚以上のカードの列を選び,次の操作を行う.

  • 選んだカードを,書かれている整数が小さい順に左から並べる.
  • 並べたカードのうち,左から K 番目のカードに書かれた整数を紙に書き出す.
  • 選んだカードを,すべて元の位置に戻す.

この操作を,連続する K 枚以上のカードの列すべてに対して行う.すなわち,1 ≦ l ≦ r ≦ N かつ K ≦ 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 行で出力せよ.

入出力例

入力例 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) は,(1,3), (1,4), (2,4)3 通りある.

これらの (l,r) に対し,a_l, a_{l+1}, ..., a_r3 番目に小さな整数は,それぞれ 4, 3, 3 である.

このうち L (= 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

である.このうち L (= 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