問題文

横一列に並べられた $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