가로로 한 줄에 늘어선 카드가 \(N\)장 있다. 왼쪽에서 \(i\)번째 (\(1 \le i \le N\)) 카드에는 정수 \(a_i\)가 적혀 있다. JOI 군은 이 카드로 다음 게임을 한다. 연속한 \(K\)장 이상의 카드 구간을 고르고 다음을 한다.
이 조작을 연속한 \(K\)장 이상의 카드 구간 모두에 대해 한다. 즉 \(1 \le l \le r \le N\)이고 \(K \le r-l+1\)인 모든 \((l,r)\)에 대해, \(a_l, a_{l+1}, \ldots, a_r\) 가운데 \(K\)번째로 작은 정수를 적는다. 이렇게 적은 정수를 작은 것부터 왼쪽에 늘어놓는다. 늘어놓은 정수 가운데 왼쪽에서 \(L\)번째가 이 게임에서 JOI 군의 점수이다. JOI 군의 점수를 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(K\) \(L\)
\(a_1\) \(a_2\) \(\cdots\) \(a_N\)
- 첫째 줄에 정수 \(N\), \(K\), \(L\)이 공백 하나로 구분되어 주어진다.
- 둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \ldots, a_N\)이 공백 하나로 구분되어 주어진다.
- \(1 \le N \le 200000\)
- \(1 \le K \le N\)
- \(1 \le a_i \le N\)
- \(1 \le L\)
- JOI 군이 적는 정수는 \(L\)개 이상이다.
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
첫째 줄에 JOI 군의 점수를 출력한다.
\(1 \le l \le r \le 4\)이고 \(3 \le r-l+1\)인 \((l,r)\)은 \((1,3)\), \((1,4)\), \((2,4)\) 세 가지이다. 각각에서 \(3\)번째로 작은 정수는 \(4\), \(3\), \(3\)이다. 이 가운데 \(L=2\)번째로 작은 정수는 \(3\)이다. 같은 정수가 여러 개여도 중복해서 센다.
적는 정수는 \((l,r)=(1,3)\)에서 \(5\), \((1,4)\)에서 \(2\), \((1,5)\)에서 \(2\), \((2,4)\)에서 \(5\), \((2,5)\)에서 \(4\), \((3,5)\)에서 \(4\)이다. 이 가운데 \(L=3\)번째로 작은 정수는 \(4\)이다.