In the good old days, Kang the Penguin served a boring cuisine comprising but a single type of penguin food to his N (1 ≤ N ≤ 40,000) junior penguins. Times change. Today he serves his juniors a total of M (1 ≤ M ≤ N) different types of food (conveniently numbered 1..M).
The junior penguins are picky. Penguin i has a single food preference Pi (1 ≤ Pi ≤ M) and will eat only that favorite food.
Each day at feeding time Kang converts the penguin hideout into a tastefully lit cafeteria. The penguins line up outside to enter the cafeteria in order of their previously-mentioned convenient index number.
Unfortunately, with so many types of food, cleaning up afterwards is very time-consuming. If Kang the penguin is serving K different types of food, it takes him K*K units of time to clean the hideout.
To save time, Kang serves the penguins in contiguous groups from the line. After each group, he cleans up the hideout and sets out the food for the next group (of course, he only sets out food that penguins in the any given group will eat). Determine the minimum amount of total time Kang must spend cleaning the hideout. Each group consists of the next contiguous group of penguins from the line; each penguin belongs to exactly one group; and the hideout must be cleaned up after every group, including the last one.
Input
- Line 1: Two space-separated integers: N and M
- Lines 2..N+1: Line i+1 contains a single integer: Pi
Output
Line 1: A single integer: the minimum amount of time Kang must spend cleaning up.
Sample Input 1
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
Explanation for Sample Input 1
There are four types of food and thirteen penguins in line. The first penguin prefers type 1, the second type 2, the third type 1, etc.
Sample Output 1
11
Explanation for Sample Output 1
The first four groups contain one penguin each. The fifth group contains two penguins who prefer food #2 (requiring one unit of time). The sixth group contains penguins preferring foods 3, 4, 3, 4, 3 (and requires four units of time to clean). The last two groups contain one penguin each. The total time is 11.