[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 $ 。