在 ACM ICPC 竞赛中，队伍的“脏比率”（dirt ratio）计算方式如下：首先，忽略所有队伍未通过的题目。假设队伍在比赛中通过了 $X$ 道题，并且为这些题目总共进行了 $Y$ 次提交。那么脏比率定义为 $\frac{X}{Y}$。如果一个队伍的脏比率过低，该队伍往往会获得更多的罚时，这通常对排名不利。

Little Q 是一位教练，他现在正盯着他学生队伍的提交列表。该列表仅包含题目 ID，没有说明哪次提交是错误的，哪次是正确的。然而，他假设列表中出现的所有题目最终都在比赛中被该队伍解决了。

Little Q 计算了队伍的脏比率，并因为比率过低而感到非常生气。他想找他们谈谈。为了让事情看起来更严肃，他想要选择列表的一个连续子序列。然后，他将只考虑在子序列中至少出现过一次的题目和提交，并假设对于这些题目中的每一道，最后一次提交是正确的，而之前的所有提交都是错误的。接着，Little Q 将仅基于所选的连续子序列计算脏比率。

你的任务是编写一个程序，找到能给出最低脏比率的子序列。

输入格式

第一行包含一个整数 $n$，表示提交列表的长度 ($1 \le n \le 6 \cdot 10^4$)。 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每次提交的题目 ID ($1 \le a_i \le n$)。

输出格式

输出一行，包含一个实数：最低可能的脏比率。 答案的绝对误差不得超过 $10^{-4}$。

样例

输入 1

5
1 2 1 2 3

输出 1

0.5000000000