소 데이팅

소에게 제공되는 시시한 데이팅 사이트들(eHarmoony, Moosk, Plenty of Cows 등)이 마음에 들지 않았던 Farmer John은, 소와 황소의 다양한 공통 관심사를 바탕으로 매칭하는 독자적인 알고리즘을 이용한 새로운 소 데이팅 사이트를 열기로 한다.

Bessie는 밸런타인 데이 헛간 댄스에서 함께할 파트너를 찾기 위해 이 사이트를 이용해 보기로 한다. 계정을 만든 뒤, FJ의 알고리즘은 그녀에게 $N$명의 가능한 상대 목록을 준다 ($1\leq N \leq 10^6$). 목록을 살펴본 Bessie는 각 황소가 자신의 댄스 초대를 수락할 확률이 $p\_i$ ($0\<p\_i<1$)라고 결론 내린다.

Bessie는 목록에서 연속된 구간에 속한 모든 황소에게 초대장을 보내기로 한다. 언제나처럼 순결한 그녀는 정확히 한 명의 파트너를 원한다. Bessie가 올바른 구간을 선택했을 때, 정확히 하나의 초대가 수락될 확률의 최댓값을 구하도록 도와주자.

첫 번째 줄에는 $N$이 주어진다 ($1 \leq N \leq 10^6$). 그다음 $N$개의 줄에는 $10^6$ 곱하기 $p\_i$의 값인 정수가 하나씩 주어진다.

최소 25%의 테스트 케이스에서는 $N \leq 4000$이라는 조건이 추가로 보장된다.

정확히 하나의 초대가 수락될 확률의 최댓값에 $10^6$을 곱한 값을, 가까운 정수로 내림하여 출력한다.

최대 확률은 2번째부터 3번째 소까지의 구간을 선택할 때 나온다.

참고로, 이 문제를 풀 때는 부동 소수점 정밀도에 어느 정도 주의해야 한다. "double" (64비트 부동 소수점) 이상을 사용하고, "float" (32비트 부동 소수점)은 사용하지 않는 것이 좋다.