The Long Paper Tape

After years of intense training, Little \(\zeta\) has mastered the art of brute force. In the S-PSC 2077 contest, he encountered a challenging problem titled The Long Paper Tape that perfectly suits his style.

You are given \(n\) groups of data. The \(i^{th}\) group has a scale value \(a_i\). Little \(\zeta\) designed a program that processes a contiguous segment of data from group \(l\) to group \(r\) in \(|S|^2\) time, where \(S = \{a_i \mid l \le i \le r\}\) is the set of distinct scale values in that segment. Formally, the processing time of the segment is \[ \left|\{a_i \mid l \le i \le r\}\right|^2. \] Your task is to partition the \(n\) data groups into one or more contiguous segments so that the total processing time is minimized.

inputFormat

The first line contains a single integer \(n\), the number of data groups.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the scale values of the groups.

outputFormat

Output a single integer, the minimum total processing time required to process all the data groups.

sample

1
5

1