L번째의 K번째 수

문제

가로 한 줄로 늘어놓은 $N$ 장의 카드가 있다. 왼쪽에서 $i$ 번째($1\,\,\le\,\,i\,\,\le\,\,N$) 카드에는 정수 $a_i$ 가 적혀 있다.

JOI 군은 이 카드들을 사용하여 다음과 같은 게임을 한다. 연속한 $K$ 장 이상의 카드의 열을 골라 다음 조작을 한다.

• 고른 카드를 적힌 정수가 작은 순서대로 왼쪽부터 늘어놓는다.
• 늘어놓은 카드 중에서 왼쪽에서 $K$ 번째 카드에 적힌 정수를 종이에 적는다.
• 고른 카드를 모두 원래 위치로 되돌린다.

이 조작을 연속한 $K$ 장 이상의 카드의 열 전부에 대해 수행한다. 즉, $1\,\,\le\,\,l\,\,\le\,\,r\,\,\le\,\,N$ 이고 $K\,\,\le\,\,r\,-\,l\,+\,1$ 을 만족하는 모든 $(l,r)$ 에 대해, $a_l,\,a_{l+1},\,...,\,a_r$ 중 $K$ 번째로 작은 정수를 적는다.

이렇게 적힌 정수를 왼쪽부터 작은 순서대로 늘어놓는다. 늘어놓은 정수 중에서 왼쪽에서 $L$ 번째인 것이 이 게임에서 JOI 군의 점수이다. JOI 군의 점수를 구하시오.

제한

• $1\,\,\le\,\,N\,\,\le\,\,200000$
• $1\,\,\le\,\,K\,\,\le\,\,N$
• $1\,\,\le\,\,a_i\,\,\le\,\,N$
• $1\,\,\le\,\,L$
• JOI 군이 적는 정수는 $L$ 개 이상이다.

서브태스크

서브태스크 1 [6점]

• $N\,\,\le\,\,100$

서브태스크 2 [33점]

• $N\,\,\le\,\,4000$

서브태스크 3 [61점]

• 추가 제약이 없다.

입력과 출력

입력
입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $K$ $L$
$a_1$ $a_2$ $...$ $a_N$

출력
JOI 군의 점수를 $1$ 줄로 출력한다.

예제 입력 1

4 3 2
4 3 1 2

예제 출력 1

3

$1\,\,\le\,\,l\,\,\le\,\,r\,\,\le\,\,N\,(=\,4)$ 이고 $K\,(=\,3)\,\,\le\,\,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