题目描述

本题题解已发表至 讨论区

给出一个长度为$n$的数组$a$，对于每一次操作，等概率的选择一个存在于数组中且未被删除的元素x（如：数组为{1,2,2}则第一次删除1和2的概率都为0.5），并将大于等于x的所有元素删除，当数组中所有元素被都被删除后结束操作。
要求求出删除所有元素的期望操作次数。

输入描述

第一行 一个正整数$n$表示数组大小 $(n<=1e6)$

第二行$n$个正整数表示数组$a$的元素$(0<a_i <=1e18)$

输出描述

输出一个实数,表示期望操作次数,答案误差在$10^{-6}$之内则认为正确

示例 1

输入

1
1

输出

1.00000000

示例 2

输入

3
3 1 2

输出

1.83333333