4. Коллекция статуэток

Петя приехал в экзотическую страну и решил купить памятный сувенир. В сувенирной лавке в ряд выставлены $n$ статуэток различных видов, причем статуэтка вида $t$ стоит ровно $t$ единиц местной валюты.

Петя решил купить статуэтки всех видов от $1$ до $k$. Оказалось, что Петя получит приличную скидку, если купит статуэтки, стоящие не в произвольных местах, а некоторым непрерывным отрезком (все статуэтки от какой-то позиции $l$ до $r$ включительно). Петя сразу понял, что ему может потребоваться купить несколько статуэток одного вида, повторяющиеся он решил подарить друзьям после возвращения домой.

Например, если в лавке статуэтки выставлены в порядке 1 2 2 3 3 1, и Петя хочет купить статуэтки видов от $1$ до $3$, то он может купить статуэтки с первой по четвертую позиции (при этом будут куплены две статуэтки вида $2$). Если же в лавке выставлены статуэтки 1 2 5 4 3 (вновь $k=3$), то Петя купит все 5 статуэток.

Помогите определить Пете минимальную суммарную стоимость статуэток, расположенных подряд в лавке, чтобы среди них были статуэтки всех видов от $1$ до $k$.

Гарантируется, что для всех тестовых данных ответ существует.

В первой строке записаны два целых числа $n$ и $k$ ($1 \le k \le n \le 500\,000$).

Во второй сроке записаны $n$ целых чисел $a_i$ (вид $i$-й статуэтки) ($1 \le a_i \le n$) — описания статуэток в сувенирной лавке. Статуэтки перечислены слева направо.

Гарантируется, что для всех тестовых данных ответ существует.

Выведите одно целое число — минимальную сумму в местной валюте, за которую мог бы купить статуэтки Петя (без учета будущей скидки).