Restaurant

Time limit1sMemory limit128 MB

Summary

Split a sequence of N foods into consecutive groups, where a group costs the square of its number of distinct foods, and minimize the total cost.

Level: Medium7 of 10
Topics: Dynamic programming, Divide and conquer, Two pointers, Prefix sum
Solved: No attempts yet

Problem

Farmer John's restaurant serves $M$ kinds of food to $N$ cows.

Each cow $i$ has a single favorite food $P_i$ , and Farmer John hands out the food by the following rule:

The cows entering the restaurant are split into consecutive groups in their arrival order. For example, $[1 \sim 4] / [5 \sim 7] / [8 \sim 10]$ cuts the line from the very front.
The cost of serving one group is (the number of distinct favorite foods among the cows in that group) $^2$ . In other words, treating foods as numbers, it is the square of how many distinct numbers appear in the group.

Find the minimum total cost of serving all the cows.

Input

The first line contains two integers $N$ and $M$ , separated by a space. ( $1 \le M \le N \le 40000$ )

Each of the next $N$ lines contains one favorite food $P_i$ , given in the order the cows arrive. ( $1 \le P_i \le M$ )

Output

Print, on a single line, the minimum total cost of serving all the cows.

Hint

For example, for the sample input, grouping the cows (in arrival order) as $[1]\,[2]\,[3]\,[4]\,[5, 6]\,[7, 8, 9, 10, 11]\,[12]\,[13]$ gives a total cost of $1 + 1 + 1 + 1 + 1 + 4 + 1 + 1 = 11$ .

Examples4

Example 1
Input
```
13 4
1
2
1
3
2
2
3
4
3
4
3
1
4
```
Expected output
```
11
```
Example 2
Input
```
1 1
1
```
Expected output
```
1
```
Example 3
Input
```
4 4
1
2
3
4
```
Expected output
```
4
```
Example 4
Input
```
5 2
1
2
1
2
1
```
Expected output
```
4
```