Disappointed in the lacklustre dating websites and apps currently available to cows (OkCowpid, eHarmoony, Plenty of Barns, EliteCattle), Farmer Adams decides to launch a new site based on a fancy matching algorithm matching cows and bulls according to their mootual interests.
Bessie, a cow, searching for a partner to the Guild Ball has decided to try out the site. After making an account, the algorithm has provided a list of \(N\) possible matches \((1 \leq N \leq 10^6)\). Going through the list, Bessie decides that each Bull has probability \(p_i (0 < p_i < 1)\) of accepting an invitation from her for the dance.
Bessie sends invitations to each bull in a contiguous interval of the list. Virtuous as always, Bessie wants exactly one accepted invitation. Please help Bessie maximise the probability of receiving exactly one accepted invitation.
The first line contains a single integer \(N (1 \leq N \leq 10^6)\). Each of the subsequent \(N\) lines contains \(p_i (1 \leq p_i \leq 999999)\) - the probability of the i-th bull saying 'yes' * \(10^6\).
Print \(10^6\) times the maximum probability of receiving exactly one accepted invitation, rounding down to the nearest integer.
Sample Input 1
3 300000 400000 350000
Sample Output 1
Note: The optimal in this case is selecting from the 2nd to 3rd cow.
Full credit goes to USACO (http://www.usaco.org/index.php?page=viewproblem2&cpid=924)