4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

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

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Компания <<КазЖелУгЗол>> готовит крупномаштабный-план по добыче полезных ископаемых. Компания наняла геолога Асем для исследования $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_{1 <= l <= r <= n}f_k(l, r)$ для какого то $k$ (суммарное значение $f_k(l, r)$ по всем отрезкам $(l, r)$). Асем уверенна в корректности значений $c_i$. Помогите написать программу для эффективного подсчета значения $S$.

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

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

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

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

Система оценки

Данная задача содержит $9$ подзадач, в которых выполняются следующие ограничения:

1. Тесты из условия. Оценивается в $0$ баллов.
2. $n <= 100$. Оценивается в $11$ баллов.
3. $n <= 5000$, $k = 1$. Оценивается в $11$ баллов.
4. $n <= 5000$. Оценивается в $12$ баллов.
5. $n <= 10^5$, $k = 1$. Оценивается в $15$ балла.
6. $n <= 10^5$, $k = 2$. Оценивается в $10$ баллов.
7. $n <= 10^5$, $a_i <= 2$. Оценивается в $9$ баллов.
8. $n <= 10^5$, $a_i <= 500$. Оценивается в $14$ баллов.
9. Исходные условия задачи. Оценивается в $18$ баллов.

Примеры:

Вход

5 3
1 2 3 2 1

Ответ

10

Вход

7 4
1 1 1 1 1 1 1

Ответ

10

Замечание

В первом примере $f_3(1, 3) = f_3(3, 5)= 1, f_3(1, 4) = f_3(1, 5) = f_3(2, 4) = f_3(2, 5) = 2$. ( Daniyar Zakarin )