데이팅 사이트

현재 서비스 중인 데이팅 웹사이트들에 만족하지 못한 한 개발자는 다양한 공통의 관심사에 따라 짝짓는 매칭 알고리즘을 기반으로 한 새로운 데이팅 사이트를 출시하기로 결정하였습니다.

발렌타인 데이에 데이트할 파트너를 찾고 있는 화영은 이 사이트를 이용해보기로 했습니다. 그녀가 계정을 만든 후, 데이팅 사이트의 알고리즘은 그녀에게 $N$ 개의 가능한 매칭 ($1 \leq N \leq 10^6$) 리스트를 제공했습니다. 목록을 훑어 보면서 화영은 리스트의 사람들이 그녀의 데이트 초대를 수락할 확률이 $p_i$ ($0\ltp_i\lt1$)라는 사실을 알았습니다.

화영은 목록의 연속적인 구간에 있는 각 사람에게 초대장을 보내기로 결정합니다. 그녀는 정확히 한 명의 파트너를 원합니다. 그녀가 올바른 구간을 선택한다면, 정확히 한 명의 초대장을 수락받을 최대 확률을 찾아 화영을 도와주세요.

입력의 첫 번째 줄에는 $N$ ($1 \leq N \leq 10^6$)이 포함되어 있습니다. 

나머지 $N$ 줄 각각에는 $10^6$ 번 $p_i$가 포함되어 있으며, 이는 정수입니다.

테스트 케이스의 적어도 25%에서는 $N \leq 4000$이 보장됩니다.

받아들여진 정확히 하나의 초대를 받는 최대 확률을 $10^6$번 곱하여, 가장 가까운 정수로 반올림하여 출력합니다.