Contiguous Group Cleaning

Farmer John used to feed his N prize dairy cows a boring cuisine consisting of only one type of cow food. Today, he serves M different types of food (numbered 1..M). The i-th cow has a food preference P_i and will only eat that food. The cows line up in order of their index. To save time cleaning the barn, Farmer John serves the cows in contiguous groups. For each group, he only sets out the food types that appear in that group. However, cleaning up afterwards takes time proportional to the square of the number of different food types served in that group. In other words, if a group contains K distinct food types, cleaning takes \(K^2\) units of time.

Your task is to partition the line of cows into one or more contiguous groups so that the total cleaning time is minimized. Note that every cow must belong to exactly one group and the barn is cleaned after every group (including the last one).

Input Format

The first line contains two integers N and M (1 \(\le\) N \(\le\) 40000, 1 \(\le\) M \(\le\) N) representing the number of cows and the number of different food types, respectively.

The second line contains N space‐separated integers P₁, P₂, ..., P_N (1 \(\le\) P_i \(\le\) M) where P_i is the favorite food of cow i.

Output Format

Output a single integer, the minimum total cleaning time Farmer John must spend.

inputFormat

The input is read from standard input. The first line contains two space‐separated integers N and M. The second line contains N space‐separated integers representing the food preferences of the cows.

outputFormat

Output a single integer – the minimum total cleaning time required.

sample

5 3
1 2 1 3 2

8