Hẹn Hò Valentine

Bessie muốn mời đúng một chàng bò trong số $N$ chàng bò đến dự vũ hội Valentine. Mỗi chàng bò $i$ có xác suất chấp nhận là $p_i$ (cho trước dưới dạng số nguyên $p_i\times {10}^6$). Bessie sẽ mời tất cả các chàng bò trong một đoạn liên tiếp $[l,r]$ và muốn xác suất để đúng một chàng chấp nhận là lớn nhất có thể.

Dữ liệu vào

• Dòng đầu: số nguyên $N$ ($1\le N\le {10}^6$)
• $N$ dòng tiếp theo, dòng $i$ chứa số nguyên $p_i\times {10}^6$ (với $0<p_i<1$)

Dữ liệu ra

Một số nguyên: giá trị xác suất tối đa nhân ${10}^6$, lấy phần nguyên (floor).

Ràng buộc

• $1\le N\le {10}^6$
• $0<p_i\times {10}^6<{10}^6$

Ví dụ