Interval Diversity

You are given an integer sequence $A_1, A_2, \cdots, A_N$ of length $N$.

For every non-empty interval $[l,r]$, define the following values.

• $x$: the number of distinct integers appearing in $A_l, A_{l+1}, \cdots, A_r$

Find the maximum value of $\dfrac{x^2}{y}$ over all possible intervals $[l,r]$.

The input is given in the following format.

$N$ $A_1\ A_2\ \cdots\ A_N$

Print the maximum value of $\dfrac{x^2}{y}$ over all non-empty intervals $[l,r]$.

Your answer is considered correct if its absolute or relative error is at most .

• $1 \le N \le 5\,000$.
• $-1\,000\,000\,000 \le A_i \le 1\,000\,000\,000$ ().