CF868F 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.

无

无

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 $ .