Cow Dating
Cow Dating
Not impressed by the lackluster dating websites currently available to cows (e.g., eHarmoony, Moosk, Plenty of Cows), Farmer John decides to launch a new cow dating site based on a fancy proprietary matching algorithm that matches cows and bulls according to a wide range of their mutual interests.
Bessie, in searching for a partner to the Valentine’s Day Barn Dance, has decided to try out this site. After making her account, FJ’s algorithm has given her a list of n possible matches. Going through the list, Bessie concludes that each bull has probability pi
of accepting an invitation from her for the dance.
Bessie decides to send an invitation to each bull in a contiguous interval of the list. Virtuous as always, she wants exactly one partner. Please help Bessie find the maximum probability of receiving exactly one accepted invitation, if she chooses the right interval.
Input
The first line contains n (1 ≤ n ≤ 106
). Each of the remaining n lines contain 106
times pi
(0 < pi
< 1), which is an integer.
Output
Print 106
times the maximum probability of receiving exactly one accepted invitation, rounded down to the nearest integer.
Explanation
The maximal probability results from selecting the interval from the 2-nd to the 3-rd cow.
3 300000 400000 350000
470000