P5242 [USACO19FEB] Cow Dating P

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.

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

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