Дан массив \(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\) принадлежит ровно одному отрезку, а сумма стоимостей отрезков минимальна.
Выходные данные
Выведите минимальную возможную сумму стоимостей.
Примечание
В первом примере мы можем разделить массив на \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 2
1 6 6 4 6 6 6
|
3
|
|
2
|
7 4
5 5 5 5 2 3 3
|
1
|