Дан массив из n чисел a1... an. Стоимостью подотрезка элементов в массиве назовем количество неупорядоченных пар различных позиций внутри подотрезка, содержащих одинаковые элементы. Разбейте массив на k непересекающихся непустых подотрезков таких, что сумма их стоимостей минимальна. Каждый элемент массива должен попасть ровно в один подотрезок.
Примечание
В первом примере оптимально разбить последовательность на три подпоследовательности: [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.