Problem Description

Since the current dating websites available to the cows did not impress Farmer John, he decided to launch a cow dating website based on a new matching algorithm. This algorithm matches bulls and cows based on their shared interests.

When Bessie was looking for a partner for the Valentine’s Day Barn Dance, she decided to try this website. After registering an account, FJ’s algorithm produced a matching list of length $N$ ($1 \leq N \leq 10^6$). For each bull on the list, the probability that he will accept her dance invitation is $p$ ($0 < p < 1$).

Bessie decides to send invitations to the cows in one continuous interval of the list, but she wants exactly one cow to accept the invitation. Please help Bessie find the maximum probability that exactly one cow accepts the invitation.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain an integer, meaning the value of $p_i$ multiplied by $10^6$.

Output Format

Output the result of taking the maximum probability that exactly one cow accepts the invitation, multiplying it by $10^6$, and then rounding down to an integer.

3
300000
400000
350000

470000

Hint

In the sample, the optimal plan is to send invitations to the second and third cows.

Subtasks: For $25\%$ of the testdata, $N \leq 4000$.

Translated by ChatGPT 5