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$
• $y$: the length of the interval, that is, $r-l+1$

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 $10^{-9}$.

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