Description

After years of brute force training, Little $ζ$ has mastered the art. During SPSC 2077, he was delighted to find that the second problem, “The Long Paper Tape,” was a challenging one - perfect for a brute force specialist like him.

This is a multiple test case problem with $n$ test cases in one test point. The size of the i-th test case is $a_i$. He wrote a brute force program where, for a continuous segment of data, the time needed to solve that segment is the square of the number of different $a_i$ values in that segment. Formally, for a continuous segment from the l-th to the r-th test case, let $S = \{a_i|l ≤ i ≤ r\}$, the program needs $|S|^2$ time to solve them together.

Now, given $n$ and the sizes of $n$ test cases, find a way to divide these cases into several segments so that the total time consumed by the program is minimized.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers $a_i$, representing the size of each test case.

Output Format

Output one number representing the minimum total time consumption.

5
1 2 3 4 5

5

6
1 2 2 1 2 3

5

9
1 2 1 4 1 2 1 1 2

8

21
1 2 1 2 1 2 1 2 1 2 3 4 5 6 7 1 2 1 2 1 2

13

Hint

「Sample 3 Explanation」

The segments are:

• First segment $\{1\}$, cost = $1$;
• Second segment $\{2\}$, cost = $1$;
• Third segment $\{1\}$, cost = $1$;
• Fourth segment $\{4\}$, cost = $1$;
• Fifth segment $\{1, 2, 1, 1, 2\}$, cost = $4$;

Therefore, the total time consumption is $8$.

「Data Constraints」

For 100% of test cases：$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。

Special Property A: All $a_i$ are randomly generated with uniform distribution in range $[1, 10^9]$, and this subtask has only one test point.

Special Property B: $1 ≤ a_i ≤ 1000$.