Не впечатленный тусклыми сайтами знакомств, доступными в настоящее время для коров (например, eHarmoony, Moosk, Plenty of Cows), фермер Джон решил запустить новый сайт знакомств с коровами, основанный на причудливом запатентованном алгоритме сопоставления, который сопоставляет коров и быков по широкому диапазону их взаимных интересов.
Бесси, ища партнера на День святого Валентина, решила попробовать этот сайт. После создания аккаунта алгоритм FJ дал ей список n возможных совпадений. Просматривая список, Бесси приходит к выводу, что каждый бык с вероятностью p[i]
примет от нее приглашение на танец.
Бесси решает отправить приглашение каждому быку на некотором отрезке списка. Как всегда добродетельная, она хочет только одного партнера. Помогите Бесси найти максимальную вероятность получить ровно одно принятое приглашение, если она выберет правильный интервал.
Первая строка содержит число n (1 ≤ n ≤ 10^6
). Каждая из следуюших n строк содержит 10^6
умноженное на p[i]
(0 < p[i]
< 1), являющееся целым числом.
Выведите 10^6
, умноженное на максимальную вероятность получения ровно одного принятого приглашения, округленное до ближайшего целого числа.
Максимальная вероятность получается при выборе интервала от 2 - ой до 3 - ей коровы.