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

Дан массив из n чисел a1... an. Стоимостью подотрезка элементов в массиве назовем количество неупорядоченных пар различных позиций внутри подотрезка, содержащих одинаковые элементы. Разбейте массив на k непересекающихся непустых подотрезков таких, что сумма их стоимостей минимальна. Каждый элемент массива должен попасть ровно в один подотрезок.

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

Первая строка содержит два целых числа n и k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20))  — размер массива и количество отрезков, на которые надо его разбить.

Следующая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n)  — элементы массива.

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

Выведите одно число  — минимальную стоимость разбиения массива на подотрезки.

Примеры
Входные данные
7 3
1 1 3 3 3 2 1
Выходные данные
1
Входные данные
10 2
1 2 1 2 1 2 1 2 1 2
Выходные данные
8
Входные данные
13 3
1 2 2 2 1 2 1 1 1 2 2 1 1
Выходные данные
9
Примечание

В первом примере оптимально разбить последовательность на три подпоследовательности: [1], [1, 3], [3, 3, 2, 1]. Стоимости равны 0, 0 и 1, поэтому ответ равен 1.

Во втором примере оптимально разбить подпоследовательность на две половины. Стоимость каждой половины равна 4.

В третьем примере оптимально разбить следующим образом: [1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]. Стоимости равны 4, 4, 1.