Background

Little $ζ$ is an OIer who loves brute force solutions. During each mock competition, he follows the philosophy of “if I can’t figure out the optimal solution in 10 minutes, I’ll submit a brute force one,” consistently achieving high scores.

During practice, he pays special attention to partial scores, solving tasks specifically for these partial points. Sometimes, he spends more time optimizing for partial scores than thinking about the complete solution.

Problem 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$.