Есть $n$ хулува (братьев-тыкв), боевая сила $i$-го из которых равна $p_i$. Они рождаются утром $i$-го дня. Гарантируется, что сумма всех $p_i$ равна $1$.
Вечером $i$-го дня уже родившиеся хулува могут выбрать: либо накопить силы (подождать до завтра), либо всем вместе отправиться на спасение дедушки. Если суммарная сила участвующих в спасении хулува равна $P$, то вероятность спасти дедушку составляет $P$, а вероятность неудачи — $1-P$. В случае неудачи все участвовавшие в спасении хулува будут схвачены демоном и больше не смогут участвовать в спасательных операциях.
Однако демон решает судьбу дедушки с помощью «русской рулетки». А именно, демон сначала случайным образом выбирает целое число $x$ от $1$ до $n$ с равномерным распределением, а затем убивает дедушку в полдень $x$-го дня. Если дедушка уже был убит, спасательная операция хулува заведомо проваливается. Хулува не знают значения $x$.
Помогите им рассчитать стратегию спасения, которая максимизирует вероятность спасения дедушки.
Входные данные
В первой строке введено целое число $n$.
В следующей строке введены $n$ десятичных дробей $p_i$.
Выходные данные
Выведите десятичную дробь, представляющую вероятность спасения дедушки при оптимальной стратегии. Ваш ответ будет считаться верным, если абсолютная или относительная погрешность не превышает $10^{-6}$.
Примеры
Пример 1
Входные данные
1 1
Выходные данные
0
Пример 2
Входные данные
7 0.5 0.5 0 0 0 0 0
Выходные данные
0.71428571428571430157
Примечание к примеру 2
Оптимальная стратегия — отправиться на спасение вдвоем на второй день. В этом случае, если дедушка еще не убит, спасение гарантированно успешно. Вероятность успешного спасения составляет $5/7$.
Пример 3
Входные данные
7 0.537354 0.277078 0.124580 0.046589 0.012498 0.001853 0.000048
Выходные данные
0.59878460205905026381
Ограничения
Для $30\%$ данных гарантируется $n \leq 3$.
Для $60\%$ данных гарантируется $n \leq 15$.
Для $100\%$ данных гарантируется $n \leq 1000$.
Гарантируется, что $\sum p_i = 1$, а количество знаков после запятой не превышает $6$.