Республиканская олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Геологическое исследование

Компания «КазЖелУгЗол» готовит крупномаштабный-план по добыче полезных ископаемых. Компания наняла геолога Асем для исследования $n$ месторождений. Для $i$-го месторождения из списка компании Асем определила оценку $c_i$ – ожидаемый объем добычи. Поскольку необходимо построить склад возле месторождений, было решено что работа по добыче будет проходить в последовательных месторождениях из списка.

Тем временем отдел финансовой аналитики компании разработал оценку плана $f_k(l, r)$ равную $k$ -му по убыванию значению среди чисел $c_l, c_{l+1}, ..., c_r$. Если в отрезке от $l$ до $r$ менее $k$ чисел, значение $f_k(l, r)$ равно нулю.

Директору компании стало интересно, чему равно значение $S = \sum_{i = l}^{i \leq r}$ $f_k(l, r)$ для какого то $k$ (суммарное значение $f_k(l, r)$ по всем отрезкам $(l, r)$). Асем уверенна в корректности значений $c_i$.

Помогите написать программу для эффективного подсчета значения $S$.

Формат входного файла

В первой строке даны два числа $n$ и $k(1 \leq n \leq 10^5, 1 \leq k \leq min(n, 500))$. Во второй строке даны $n$ чисел $c_1$, $c_2$, ..., $c_n$ – оценки месторождений $(1 \leq c_i \leq 10^7)$ .

Формат выходного файла

Выведите одно число $S$.

Примеры

Вход

5 3
1 2 3 2 1

Выход

10

Вход

7 4
1 1 1 1 1 1 1

Выход

10