Побачення з коровами
Не вражена існуючими сайтами знайомств для корів, такими як 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-ої корови.