Yet Another Minimization Problem

n개의 정수로 이루어진 배열 a1... an이 주어진다. 한 부분 구간의 비용은 그 부분 구간 안에서 원소가 같은 서로 다른 인덱스의 순서 없는 쌍의 수이다. 주어진 배열을 서로 겹치지 않는 비어 있지 않은 k개의 부분 구간으로 나누어, 그 비용의 합이 가능한 한 최소가 되게 한다. 각 원소는 정확히 하나의 부분 구간에 포함되어야 한다.

첫 번째 줄에는 두 정수 n와 k가 주어진다(2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20)). 이는 배열의 길이와 배열을 나누어야 하는 구간의 수이다.

다음 줄에는 배열의 원소인 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ n)가 주어진다.

결과 부분 구간들의 가능한 최소 총비용을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 수열을 다음 세 부분 구간으로 나누는 것이 최적이다: $[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이다.