카드 N장이 가로로 한 줄 놓여 있다. 왼쪽에서 i번째 카드(1≤i≤N)에는 정수 ai가 적혀 있다.
이 카드로 다음 게임을 한다. 연속한 K장 이상의 카드를 고른 뒤, 아래 조작을 한다.
- 고른 카드를 적힌 정수가 작은 순서대로 왼쪽부터 늘어놓는다.
- 늘어놓은 카드 중 왼쪽에서 K번째 카드에 적힌 정수를 종이에 적는다.
- 고른 카드를 모두 원래 자리로 되돌린다.
연속한 K장 이상인 카드 구간 전체에 이 조작을 한 번씩 한다. 즉 1≤l≤r≤N이고 K≤r−l+1인 모든 (l,r)에 대해 al,al+1,…,ar 중 K번째로 작은 정수를 적는다.
이렇게 적은 정수를 작은 순서대로 늘어놓는다. 늘어놓은 정수 중 왼쪽에서 L번째 정수가 이 게임의 점수이다. 점수를 구하여라.