A11197. Yet Another Minimization Problem

You are given an array of $n$ integers $a_{1}...\ a_{n}$ . The cost of a subsegment is the number of unordered pairs of distinct indices within the subsegment that contain equal elements. Split the given array into $k$ non-intersecting non-empty subsegments so that the sum of their costs is minimum possible. Each element should be present in exactly one subsegment.

The first line contains two integers $n$ and $k$ ( $2<=n<=10^{5}$ , $2<=k<=min\ (n,20))$ — the length of the array and the number of segments you need to split the array into.

The next line contains $n$ integers $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=n$ ) — the elements of the array.

Print single integer: the minimum possible total cost of resulting subsegments.

In the first example it's optimal to split the sequence into the following three subsegments: $[1]$ , $[1,3]$ , $[3,3,2,1]$ . The costs are $0$ , $0$ and $1$ , thus the answer is $1$ .

In the second example it's optimal to split the sequence in two equal halves. The cost for each half is $4$ .

In the third example it's optimal to split the sequence in the following way: $[1,2,2,2,1]$ , $[2,1,1,1,2]$ , $[2,1,1]$ . The costs are $4$ , $4$ , $1$ .