题目描述

题目译自 USACO 2019 February Contest, Platinum Problem 1. Cow Dating

FJ 对目前为奶牛提供的乏善可陈的约会网站（如 eHarmoony、Moosk、Plenty of Cows）不以为然，决定推出一个新的奶牛约会网站，该网站基于一种花哨的专有匹配算法，根据奶牛和公牛的广泛共同兴趣进行匹配。

Bessie 在寻找情人节谷仓舞会的舞伴时，决定试试这个网站。在建立账户后，FJ 的算法给了她一个长度为 $N$ 的可能的匹配名单（$1\le N\le 10^6$）。浏览了这个列表后，Bessie 得出结论，每只公牛接受她的舞会邀请的概率是 $p_i$（$0<p_i<1$）。

Bessie 决定向名单上一段相邻的公牛发出邀请。一如既往地，她希望恰好有一个舞伴。如果 Bessie 选择了正确的区间，请帮助她计算恰好一个邀请被接受的最大概率。

输入格式

第一行包含一个正整数 $N$（$1\le N\le 10^6$）。接下来 $N$ 行，每行包含一个整数，表示 $p_i$ 乘 $10^6$ 后的值。

输出格式

输出恰好一个邀请被接受的最大概率，这个概率先乘以 $10^6$ 再下取整后输出。

3
300000
400000
350000

470000

数据范围与提示

最少有 $25\%$ 的测试数据满足 $N\le 4\cdot 10^3$。