题目描述

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