Blocos de assuntos

Time limit: 3000 msMemory limit: 256 MB

Uma programação contém $n$ palestras em ordem fixa; a palestra $i$ aborda o assunto $a_i$ . Divida a programação em exatamente $k$ blocos contíguos não vazios. O desconforto de um bloco é a quantidade de pares de posições diferentes dentro dele que abordam o mesmo assunto, contando cada par uma vez. Minimize a soma dos desconfortos dos blocos.

Input

A primeira linha contém $n,k$ . A segunda contém $a_1,\ldots,a_n$ .

, , .

Output

Imprima o menor desconforto total.

Samples

Sample 1

Input

5 2
1 2 1 2 1

Output

Os blocos $[1,2]$ e $[3,5]$ têm custos 0 e 1.