Свидания с коровами
Не впечатленный тусклыми сайтами знакомств, доступными в настоящее время для коров (например, 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 - ей коровы.