Informatica Online Judge

  L번째, K번째 수 [2154 / 086A]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : t1234 - 0ms / 513byte
My Best Submission (C++) : N/A

[JOI 2018 예선]

Background

横一列に並べられた 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 君の得点を求めよ.

Input

入力は以下の形式で標準入力から与えられる.
N K L
a_1 a_2 ... a_N

[입력값의 정의역]
1 ≦ N ≦ 200000
1 ≦ K ≦ N
1 ≦ a_i ≦ N
1 ≦ L
JOI 君が書き出す整数は L 個以上である

Output

JOI 君の得点を 1 行で出力せよ.

IO Example

入力例 1
4 3 2
4 3 1 2

出力例 1
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]