题目描述

由于目前可供奶牛们使用的约会网站并没有给 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$ 。