5. Очередная задача про кузнечика
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд стоят $$$n$$$ столбиков, пронумерованных слева направо целыми числами от $$$1$$$ до $$$n$$$. Высота $$$i$$$-го столбика равна $$$a_i$$$. Кузнечик может прыгать по столбикам только вперед (со столбика с меньшим номером на столбик с большим номером), и за один прыжок он может перепрыгнуть не более, чем на $$$k$$$ столбиков вперед. Формально, кузнечик может перепрыгнуть со столбика $$$i$$$ на столбик $$$j$$$, если $$$i \lt j$$$ и $$$j - i \le k$$$.

Кузнечик хочет быть как можно выше, поэтому он стремится максимизировать минимальную из высот посещенных им столбиков.

Обозначим за $$$f(l, r)$$$ максимум из минимальных высот посещенных столбиков по всем маршрутам кузнечика от столбика с номером $$$l$$$ до столбика с номером $$$r$$$.

Вам требуется найти значение суммы $$$\sum \limits_{l=1}^n \sum \limits_{r=l}^n f(l, r)$$$. Иными словами вы должны найти сумму значений $$$f(l, r)$$$ по всем парам столбиков $$$l$$$ и $$$r$$$ ($$$l \le r$$$).

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 200\,000, 1 \le k \le n - 1$$$) — количество столбиков и максимальное расстояние, на которое кузнечик может прыгнуть вперед.

Вторая строка содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^8$$$) — высоты столбиков.

Выходные данные

Выведите одно целое число — значение суммы $$$\sum \limits_{l=1}^n \sum \limits_{r=l}^n f(l, r)$$$.

Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
00Тесты из условияполная
15$$$n \le 5$$$первая ошибка
25$$$n \le 15$$$1первая ошибка
310$$$n \le 100$$$1, 2первая ошибка
410$$$n \le 600$$$1, 2, 3первая ошибка
510$$$n \le 5\,000, k = 1$$$первая ошибка
615$$$n \le 5\,000$$$1, 2, 3, 4первая ошибка
715$$$k = 1$$$5первая ошибка
830нет1 – 7первая ошибка
Пример
Входные данные
4 2
2 1 4 2
Выходные данные
18
Примечание

Рассмотрим пример из условия.

  • Для пары столбиков $$$[1, 1]$$$ оптимальный маршрут состоит только из первого столбика, следовательно $$$f(1, 1) = 2$$$
  • Для пары столбиков $$$[1, 2]$$$ оптимальный маршрут состоит из столбиков с номерами $$$1$$$ и $$$2$$$, следовательно $$$f(1, 2) = 1$$$
  • Для пары столбиков $$$[1, 3]$$$ оптимальный маршрут состоит из столбиков с номерами $$$1$$$ и $$$3$$$, следовательно $$$f(1, 3) = 2$$$
  • Для пары столбиков $$$[1, 4]$$$ оптимальный маршрут состоит из столбиков с номерами $$$1$$$, $$$3$$$ и $$$4$$$, следовательно $$$f(1, 4) = 2$$$
  • Для пары столбиков $$$[2, 2]$$$ оптимальный маршрут состоит только из второго столбика, следовательно $$$f(2, 2) = 1$$$
  • Для пары столбиков $$$[2, 3]$$$ оптимальный маршрут состоит из столбиков с номерами $$$2$$$ и $$$3$$$, следовательно $$$f(2, 3) = 1$$$
  • Для пары столбиков $$$[2, 4]$$$ оптимальный маршрут состоит из столбиков с номерами $$$2$$$ и $$$4$$$, следовательно $$$f(2, 4) = 1$$$
  • Для пары столбиков $$$[3, 3]$$$ оптимальный маршрут состоит только из третьего столбика, следовательно $$$f(3, 3) = 4$$$
  • Для пары столбиков $$$[3, 4]$$$ оптимальный маршрут состоит из столбиков с номерами $$$3$$$ и $$$4$$$, следовательно $$$f(3, 4) = 2$$$
  • Для пары столбиков $$$[4, 4]$$$ оптимальный маршрут состоит только из четвертого столбика, следовательно $$$f(4, 4) = 2$$$.