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.

Input Specification

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\).

Output Specification

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

470000

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)