Không ấn tượng với những trang web hẹn hò tẻ nhạt hiện dành cho bò (chẳng hạn eHarmoony, Moosk, Plenty of Cows), Farmer John quyết định ra mắt một trang hẹn hò mới dành cho bò, sử dụng một thuật toán ghép đôi độc quyền tinh vi để ghép bò cái và bò đực dựa trên rất nhiều sở thích chung của chúng.

Trong lúc tìm bạn nhảy cho Vũ hội Chuồng bò ngày Valentine, Bessie quyết định dùng thử trang web này. Sau khi cô tạo tài khoản, thuật toán của FJ cung cấp một danh sách gồm \(N\) đối tượng có thể ghép đôi (\(1\leq N \leq 10^6\)). Xem qua danh sách, Bessie kết luận rằng mỗi con bò đực có xác suất \(p_i\) (\(0<p_i<1\)) chấp nhận lời mời dự vũ hội của cô.

Bessie quyết định gửi lời mời cho mỗi con bò đực thuộc một đoạn liên tiếp trong danh sách. Vốn luôn đoan chính, cô muốn có đúng một bạn nhảy. Hãy giúp Bessie tìm xác suất lớn nhất để nhận được đúng một lời chấp nhận, nếu cô chọn đoạn thích hợp.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 10^6\)). Mỗi dòng trong \(N\) dòng còn lại chứa \(10^6\) lần \(p_i\); giá trị này là một số nguyên.

Phân nhóm

Trong ít nhất 25% số test, dữ liệu còn bảo đảm \(N \leq 4000\).

Dữ liệu ra

In ra \(10^6\) lần xác suất lớn nhất để nhận được đúng một lời chấp nhận, làm tròn xuống số nguyên gần nhất.

Ví dụ

3
300000
400000
350000

470000

Lưu ý rằng bạn nên cẩn thận đôi chút với độ chính xác số thực khi giải bài này. Ban tổ chức khuyên dùng ít nhất kiểu double (số thực dấu phẩy động 64 bit), không nên dùng kiểu float (số thực dấu phẩy động 32 bit).

Nguồn

USACO 2019 February Contest, Platinum — Cow Dating

Tác giả: Ethan Guo.