第17回日本情報オリンピック　予選６

2017年12月11日
情報オリンピック日本委員会

問題文

横一列に並べられた 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 個以上である．

入力・出力

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

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

小課題

小課題 1 [6点]

• N ≦ 100

小課題 2 [33点]

• N ≦ 4000

小課題 3 [61点]

• 追加の制限はない．

入出力例

入力例 1
4 3 2
4 3 1 2

出力例 1
3

1 ≦ l ≦ r ≦ N (= 4) かつ K (= 3) ≦ r - l + 1 を満たす (l,r) は，(1,3), (1,4), (2,4) の 3 通りある．

これらの (l,r) に対し，a_l, a_{l+1}, ..., a_r で 3 番目に小さな整数は，それぞれ 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