## Cow Dating

Points: 1
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

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)