[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 $ 后向下取整后的结果。

输入输出样例

输入样例 #1

3
300000
400000
350000

输出样例 #1

470000

说明

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