## Cow Dating

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)

## Comments