L번째 K번째 수

시간 제한2초메모리 제한512 MB

요약

N개의 카드에서 길이가 K 이상인 모든 연속 구간의 K번째로 작은 값을 모은 뒤, 그 값들 중 L번째로 작은 값을 구한다.

난이도: 어려움10점 중 9점
유형: 이분 탐색, 배열, 누적 합, 조합론
정답자: 아직 제출이 없습니다

문제

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

이 카드로 다음 게임을 한다. 연속한 $K$ 장 이상의 카드를 고른 뒤, 아래 조작을 한다.

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

연속한 $K$ 장 이상인 카드 구간 전체에 이 조작을 한 번씩 한다. 즉 $1 \le l \le r \le N$ 이고 $K \le r - l + 1$ 인 모든 $(l, r)$ 에 대해 $a_l, a_{l+1}, \dots, a_r$ 중 $K$ 번째로 작은 정수를 적는다.

이렇게 적은 정수를 작은 순서대로 늘어놓는다. 늘어놓은 정수 중 왼쪽에서 $L$ 번째 정수가 이 게임의 점수이다. 점수를 구하여라.

입력

입력은 표준 입력으로 다음 형식으로 주어진다.

N K L
a_1 a_2 ... a_N

출력

점수를 한 줄에 출력한다.

제한

$1 \le N \le 200000$
$1 \le K \le N$
$1 \le a_i \le N$
$1 \le L$
종이에 적는 정수는 $L$ 개 이상이다.

예제4

예제 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
```