Фермер Джон сделал новый сайт для коров и быков.
Беси решила воспользоваться им для поиска партнёра. Он создала аккаунт и
получила список из \(N\) возможных соответствий (\(1\leq N \leq 10^6\)).
Беси оценила, что каждый бык имеет вероятность \(p_i\) (\(0<p_i<1\))
согласиться на её приглашение на танец.
Беси решила послать приглашение каждому быку в некотором непрерывном интервале
списка, но так, чтобы получить ровно одного партнёра. Помогите Беси определить
максимальную вероятность получить ровно одно принятое приглашение,
выбрав правильный интервал.
Формат входных данных:
Первая строка ввода содержит
\(N\) (
\(1 \leq N \leq 10^6\)). Каждая из оставшихся
строк содержит
\(10^6\) умноженное на
\(p_i\), что является целым числом.
Как минимум для 25% тестов гарантировано \(N \leq 4000\).
ФОРМАТ ВЫВОДА (файл cowdate.out):
Выведите умноженную на \(10^6\) вероятность получить ровно одно принятое приглашение
округлённую вниз до ближайшего целого числа.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
300000
400000
350000
|
470000
|