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

## 输入输出样例

### 输入样例 #1

7 3
1 1 3 3 3 2 1


### 输出样例 #1

1


### 输入样例 #2

10 2
1 2 1 2 1 2 1 2 1 2


### 输出样例 #2

8


### 输入样例 #3

13 3
1 2 2 2 1 2 1 1 1 2 2 1 1


### 输出样例 #3

9


## 说明

In the first example it's optimal to split the sequence into the following three subsegments: $$ , $[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$ .