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

[problemUrl]: https://atcoder.jp/contests/joi2018yo/tasks/joi2018_yo_f 横一列に並べられた $ 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 君の得点を求めよ．

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

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

### 制約 - $ 1\ ≦\ N\ ≦\ 200000 $ - $ 1\ ≦\ K\ ≦\ N $ - $ 1\ ≦\ a_i\ ≦\ N $ - $ 1\ ≦\ L $ - JOI 君が書き出す整数は $ L $ 個以上である． ### 小課題 1 \[6点\] - $ N\ ≦\ 100 $ ### 小課題 2 \[33点\] - $ N\ ≦\ 4000 $ ### 小課題 3 \[61点\] - 追加の制限はない． ### Sample Explanation 1 $ 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 $ である．同じ整数が複数あるときも，重複して数えることに注意せよ． ### Sample Explanation 2 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 $ である．