Jolany is a little girl who lives in a faraway galaxy where the time travel (only to the future) is allowed. Today is Jolany's birthday and she received her first time travel machine as a gift from her parents.
In order to receive more gifts, she wants to use her new time machine to jump directly to her next birthday, exactly one year from now. A year on her planet has $n$ days.
Time machines on her planet have two nice properties:
Jolany set her machine to send her $n$ days to the future and then she wrote down in a piece of paper a list with the probabilities that the machine works for each of the n days.
Unfortunately, she pushed the "hard mode" button in the machine, this button hides the array of probabilities to the user and then applies a random permutation to it, know the machine won't work with the original array but with a hidden permutation of it. Notice that there are always $n!$ different and equally probable permutations of the original array.
The only information Jolany has is the original array of probabilities and she wants to know the expected number of days she needs to wait until her next birthday. Can you help her?
The first line contains integer $n$ ($1 <= n <= 5000$) — The number of days in a year in Jolany's planet.
The second line contains $n$ numbers — The original array of probabilities. Every probability is between 0 and 1 (inclusive) and has at most 4 digits after the decimal point.
Output one line containing the answer to the task. Your answer will be considered correct if the absolute or relative error is at most $10^(-6)$.
In the first example the machine will work with probability 0.2 otherwise Jonaly will need to wait one day so the answer is $0. 2 * 0 + 0. 8 * 1$.
In the second example there are 2 possible equally probable arrays [0.5, 1] with expected value $0. 5$ and [1, 0.5] with expected value $0$. So, the answer is $0. 25$.
## Input
The first line contains integer $n$ ($1 <= n <= 5000$) — The number of days in a year in Jolany's planet.The second line contains $n$ numbers — The original array of probabilities. Every probability is between 0 and 1 (inclusive) and has at most 4 digits after the decimal point.
## Output
Output one line containing the answer to the task. Your answer will be considered correct if the absolute or relative error is at most $10^(-6)$.
[samples]
## Note
In the first example the machine will work with probability 0.2 otherwise Jonaly will need to wait one day so the answer is $0. 2 * 0 + 0. 8 * 1$. In the second example there are 2 possible equally probable arrays [0.5, 1] with expected value $0. 5$ and [1, 0.5] with expected value $0$. So, the answer is $0. 25$.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 5000 $.
Let $ P = (p_1, p_2, \dots, p_n) $ be a sequence of probabilities, where $ p_i \in [0,1] $ for all $ i $.
Let $ \Pi_n $ denote the set of all $ n! $ permutations of $ P $. Each permutation $ \pi \in \Pi_n $ is equally likely with probability $ \frac{1}{n!} $.
For a permutation $ \pi = (\pi_1, \pi_2, \dots, \pi_n) $, define the waiting time $ T_\pi $ as the smallest index $ i \in \{1, 2, \dots, n\} $ such that $ \pi_i = 1 $, or $ n $ if no such $ i $ exists (i.e., the machine fails on all days).
**Constraints**
- Each $ p_i \in [0,1] $, with at most 4 decimal digits.
- All permutations of $ P $ are equally probable.
**Objective**
Compute the expected waiting time:
$$
\mathbb{E}[T] = \frac{1}{n!} \sum_{\pi \in \Pi_n} \min\{ i \in \{1, \dots, n\} : \pi_i = 1 \} \quad \text{(with } \min \emptyset = n \text{)}
$$
Equivalently, define indicator variables for success on day $ i $:
Let $ X_i $ be the event that the machine works on day $ i $ and failed on all previous days. Then:
$$
\mathbb{E}[T] = \sum_{i=1}^n i \cdot \mathbb{P}(\text{first success at day } i)
$$
where $ \mathbb{P}(\text{first success at day } i) = \mathbb{P}(\pi_i = 1 \text{ and } \pi_j < 1 \text{ for all } j < i) $, averaged over all permutations.
By symmetry and linearity of expectation, the probability that the first success occurs on day $ i $ is proportional to the number of ways to assign the values such that the first $ i-1 $ values are strictly less than 1 and the $ i $-th is 1. However, since values may not be distinct and some may be 1, we define:
Let $ k = |\{ j : p_j = 1 \}| $.
Then, the machine will eventually succeed on some day if $ k \geq 1 $.
The expected waiting time is:
$$
\mathbb{E}[T] = \sum_{i=1}^n \mathbb{P}(\text{no success in first } i-1 \text{ days})
$$
This holds because for any nonnegative integer-valued random variable $ T $, $ \mathbb{E}[T] = \sum_{i=0}^{n-1} \mathbb{P}(T > i) $.
Let $ q_i = \mathbb{P}(\text{day } i \text{ fails}) $. But since the permutation is random, the probability that the first $ m $ days all fail is the probability that all $ m $ selected values are from the non-1 probabilities.
Let $ s = n - k $, the number of non-1 probabilities.
Then:
$$
\mathbb{P}(\text{first } m \text{ days fail}) = \begin{cases}
\frac{\binom{s}{m} m! (n - m)!}{n!} = \frac{\binom{s}{m}}{\binom{n}{m}} & \text{if } m \leq s \\
0 & \text{if } m > s
\end{cases}
$$
Actually, simpler: the probability that the first $ m $ positions contain only non-1 values is:
$$
\mathbb{P}(T > m) = \frac{\binom{s}{m} m! (n - m)!}{n!} = \frac{s! / (s - m)!}{n! / (n - m)!} = \frac{s^{\underline{m}}}{n^{\underline{m}}}
$$
where $ x^{\underline{m}} = x(x-1)\cdots(x-m+1) $ is the falling factorial.
Thus:
$$
\boxed{\mathbb{E}[T] = \sum_{m=0}^{s} \frac{s^{\underline{m}}}{n^{\underline{m}}}}
$$
where $ s = \#\{ j : p_j < 1 \} $, and $ s^{\underline{0}} = 1 $.
If $ k = 0 $ (no success possible), then $ T = n $ always, so $ \mathbb{E}[T] = n $. But the problem implies at least one success is possible (since she wants to reach next birthday), and examples include 1s.
So final formal objective:
Let $ s = \text{number of probabilities strictly less than } 1 $.
Then:
$$
\mathbb{E}[T] = \sum_{m=0}^{s} \prod_{j=0}^{m-1} \frac{s - j}{n - j}
$$