레이팅 미적용설명
横一列に並べられた 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 ≦ N ≦ 200000
1 ≦ K ≦ N
1 ≦ a_i ≦ N
1 ≦ L
JOI 君が書き出す整数は L 個以上である.
入力・出力
小課題 1 [6点]
N ≦ 100
小課題 2 [33点]
N ≦ 4000
小課題 3 [61点]
追加の制限はない.
입력 형식
入力は以下の形式で標準入力から与えられる.
N K L
a_1 a_2 ... a_N
출력 형식
JOI 君の得点を 1 行で出力せよ.
예제 1
입력
4 3 2
4 3 1 2
출력
3
예제 2
입력
5 3 3
1 5 2 2 4
출력
4
예제 3
입력
6 2 9
1 5 3 4 2 4
출력
4
예제 4
입력
6 2 8
1 5 3 4 2 4
출력
3
문제 정보