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

Есеп A. Геологиялық зерттеу

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

1 second

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

256 megabytes

<<КазЖелУгЗол>> компаниясы пайдалы қазбаларды өндіру бойынша ірі ауқымды жоспар дайындауда. Компания $n$ кен орындарын зерттеу үшін геолог Асемді жалдады. Компания тізіміндегі $i$-ші кен орнының күтілетін өндіру көлемін Асем $c_i$-ға бағалады. Кен орындарының жанында қойма салу қажет болғандықтан, өндіру жұмыстары тізімде қатар орналасқан кен орындарында өтеді деп шешілді. Сонымен бірге, компанияның қаржылық талдау бөлімі $f_k(l, r)$-ді $c_l, c_{l + 1}, ..., c_r$ сандары арасындағы мәнінің кемуі бойынша $k$-ші санға тең деп шешті. Егер $l$-дан $r$-ға дейінгі кесіндіде $k$-дан кем сан болса, $f_k(l, r)$ мәні нөлге тең болады. Компания директоры қандай да бір $k$ үшін $S = \sum_{1 <= l <= r <= n}f_k(l, r)$ мәнін білгісі келді (барлық $(l, r)$ кесінділері үшін $f_k(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 )