E. Игра в разделения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ из $$$n$$$ целых чисел. Стоимость массива $$$t$$$ вычисляется следующим образом:

$$$$$$cost(t) = \sum_{x \in set(t) } last(x) - first(x),$$$$$$

где $$$set(t)$$$ есть множество всех различных значений в $$$t$$$ без повторений, $$$first(x)$$$, и $$$last(x)$$$ индексы первого и последнего вхождения $$$x$$$ в $$$t$$$, соответственно. Другими словами, мы считаем сумму расстояний между первым и последним вхождением каждого значения.

Вам нужно разделить $$$a$$$ на $$$k$$$ последовательных отрезков так, что каждый элемент $$$a$$$ принадлежит ровно одному отрезку, а сумма стоимостей отрезков минимальна.

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

Первая строка содержит целые числа $$$n$$$, $$$k$$$ ($$$1 \le n \le 35\,000$$$, $$$1 \le k \le \min(n,100)$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$).

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

Выведите минимальную возможную сумму стоимостей.

Примеры
Входные данные
7 2
1 6 6 4 6 6 6
Выходные данные
3
Входные данные
7 4
5 5 5 5 2 3 3
Выходные данные
1
Примечание

В первом примере мы можем разделить массив на $$$[1,6,6,4]$$$ и $$$[6,6,6]$$$. Стоимость $$$[1,6,6,4]$$$ будет $$$(1-1) + (3 - 2) + (4-4) = 1$$$, а стоимость $$$[6,6,6]$$$ будет $$$3-1 = 2$$$. Суммарная стоимость будет $$$1 + 2 = 3$$$.

Во втором примере разделим массив на $$$[5,5],[5],[5,2,3]$$$ и $$$[3]$$$. Суммарная стоимость будет $$$1 + 0 + 0 + 0 = 1$$$.