구간 다양도

길이 $N$의 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.

모든 길이 $1$ 이상의 구간 $[l,r]$에 대해 다음 값을 정의하자.

• $x$: $A_l, A_{l+1}, \cdots, A_r$에 등장하는 서로 다른 정수의 개수
• $y$: 구간의 길이, 즉 $r-l+1$

모든 가능한 구간 $[l,r]$에 대해 $\dfrac{x^2}{y}$의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

모든 길이 $1$ 이상의 구간 $[l,r]$에 대한 $\dfrac{x^2}{y}$의 최댓값을 출력한다.

정답과의 절대 오차 또는 상대 오차가 $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$).