{"raw_statement":[{"iden":"statement","content":"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.\n\nIn 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.\n\nTime machines on her planet have two nice properties: \n\nJolany 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.\n\nUnfortunately, 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.\n\nThe 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?\n\nThe first line contains integer $n$ ($1 <= n <= 5000$) — The number of days in a year in Jolany's planet.\n\nThe 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.\n\nOutput 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)$.\n\nIn 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$. \n\nIn 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$.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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)$."},{"iden":"examples","content":"Input1\n0.2\nOutput0.800000000000\nInput2\n0.5 1.0\nOutput0.250000000000\nInput3\n0.3 0.1 0.1\nOutput2.090333333333\n"},{"iden":"note","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 5000 $.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a sequence of probabilities, where $ p_i \\in [0,1] $ for all $ i $.  \n\nLet $ \\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!} $.  \n\nFor 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).  \n\n**Constraints**  \n- Each $ p_i \\in [0,1] $, with at most 4 decimal digits.  \n- All permutations of $ P $ are equally probable.  \n\n**Objective**  \nCompute the expected waiting time:  \n$$\n\\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{)}\n$$  \nEquivalently, define indicator variables for success on day $ i $:  \nLet $ X_i $ be the event that the machine works on day $ i $ and failed on all previous days. Then:  \n$$\n\\mathbb{E}[T] = \\sum_{i=1}^n i \\cdot \\mathbb{P}(\\text{first success at day } i)\n$$  \nwhere $ \\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.  \n\nBy 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:  \n\nLet $ k = |\\{ j : p_j = 1 \\}| $.  \nThen, the machine will eventually succeed on some day if $ k \\geq 1 $.  \n\nThe expected waiting time is:  \n$$\n\\mathbb{E}[T] = \\sum_{i=1}^n \\mathbb{P}(\\text{no success in first } i-1 \\text{ days})\n$$  \nThis holds because for any nonnegative integer-valued random variable $ T $, $ \\mathbb{E}[T] = \\sum_{i=0}^{n-1} \\mathbb{P}(T > i) $.  \n\nLet $ 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.  \n\nLet $ s = n - k $, the number of non-1 probabilities.  \n\nThen:  \n$$\n\\mathbb{P}(\\text{first } m \\text{ days fail}) = \\begin{cases}\n\\frac{\\binom{s}{m} m! (n - m)!}{n!} = \\frac{\\binom{s}{m}}{\\binom{n}{m}} & \\text{if } m \\leq s \\\\\n0 & \\text{if } m > s\n\\end{cases}\n$$  \nActually, simpler: the probability that the first $ m $ positions contain only non-1 values is:  \n$$\n\\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}}}\n$$  \nwhere $ x^{\\underline{m}} = x(x-1)\\cdots(x-m+1) $ is the falling factorial.  \n\nThus:  \n$$\n\\boxed{\\mathbb{E}[T] = \\sum_{m=0}^{s} \\frac{s^{\\underline{m}}}{n^{\\underline{m}}}}\n$$  \nwhere $ s = \\#\\{ j : p_j < 1 \\} $, and $ s^{\\underline{0}} = 1 $.  \n\nIf $ 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.  \n\nSo final formal objective:  \n\nLet $ s = \\text{number of probabilities strictly less than } 1 $.  \nThen:  \n$$\n\\mathbb{E}[T] = \\sum_{m=0}^{s} \\prod_{j=0}^{m-1} \\frac{s - j}{n - j}\n$$","simple_statement":"Jolany wants to travel exactly one year (n days) into the future.  \nShe has a time machine that tries to jump forward one day at a time, each day with a given probability of success.  \nBut the machine randomly shuffles the probabilities before use — all n! orderings are equally likely.  \n\nGiven the original list of n probabilities, find the expected number of days she must wait until the machine succeeds (i.e., until the first successful jump).  \n\nOutput the expected value with error ≤ 1e-6.","has_page_source":false}