[USACO19FEB] Cow Dating P

由于目前可供奶牛们使用的约会网站并没有给 Farmer John 留下深刻印象，他决定推出一个基于新匹配算法的奶牛交友网站，该算法可基于公牛和母牛间的共同兴趣对公牛和母牛进行匹配。 Bessie 在寻找情人节 Barn Dance 的合作伙伴时，决定试用这个网站。在注册账户之后，FJ 的算法为他给出了一个长度为 $ N $（$1 \leq N \leq 10^6$） 的匹配列表，列表上每头公牛接受她舞蹈邀请的概率为 $ p $（$0 < p < 1$）。 Bessie 决定向列表中的一个连续区间内的奶牛发送邀请，但Bessie希望**恰好只有一个奶牛**接受邀请。请帮助 Bessie 求出**恰好只有一个奶牛**接受邀请的最大概率是多少。

第一行输入一个整数 $ N $ 。 接下来 $ N $ 行，每行包含一个整数，它的含义是 $ p_i $ 乘以 $ 10^6 $ 后的结果。

请输出**恰好只有一个奶牛**接受邀请的最大概率乘以 $ 10^6 $ 后向下取整后的结果。

3
300000
400000
350000

470000

样例的最优方案是向第二和第三只奶牛发送邀请。 子任务：对于 $ 25\% $ 的数据， $ N \leq 4000 $ 。