L번째 K번째 수

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

어려움9이분 탐색배열누적 합조합론아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

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

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

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

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

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

입력

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

N K L
a_1 a_2 ... a_N

출력

점수를 한 줄에 출력한다.

제한

  • 1N2000001 \le N \le 200000
  • 1KN1 \le K \le N
  • 1aiN1 \le a_i \le N
  • 1L1 \le L
  • 종이에 적는 정수는 LL개 이상이다.