Chiến thuật thắng cuộc

Một đội tuyển thi đấu lập trình luôn gồm đúng $n$ thành viên. Mỗi người chỉ được phép dự vòng chung kết tối đa hai lần trong đời.

Người ta thống kê được: nếu một đội có $i$ thành viên đã từng dự chung kết trước đó (và $n-i$ thành viên còn lại lần đầu dự thi) thì xác suất giành huy chương của đội là $p_i$. Biết rằng $p_0\le p_1\le \dots \le p_n$.

Trường có nguồn sinh viên vô hạn và muốn cử đội đi thi vô hạn nhiều lần (năm $1,2,3,\dots$). Ở năm thứ $k$, đội gồm $a_k$ thành viên đã từng dự thi (với $0\le a_k\le n$) và $n-a_k$ thành viên lần đầu. Sau năm đó:

• $a_k$ người đã từng dự thi này giờ đã dùng hết hai lần, không thể tham dự nữa.
• $n-a_k$ người lần đầu trở thành "đã từng dự thi một lần", có thể được dùng cho các năm sau.

Nói cách khác, mỗi năm ta tiêu thụ $a_k$ người thuộc kho "đã dự một lần" và bổ sung $n-a_k$ người mới vào kho đó; kho này không bao giờ được âm.

Hãy chọn dãy chiến thuật $a_1,a_2,\dots$ sao cho giới hạn xác suất trung bình giành huy chương mỗi năm

$$\Psi ={lim}_{m\to \infty }\frac{1}{m}\sum _{k=1}^m{p}_{a_k}$$

tồn tại và đạt giá trị lớn nhất. In ra giá trị lớn nhất đó.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n+1$ số thực $p_0,p_1,\dots ,p_n$ (mỗi số có không quá 6 chữ số sau dấu chấm), thỏa mãn $p_i\le p_{i+1}$ với mọi $0\le i\le n-1$.

Dữ liệu ra

• In ra một số thực: giá trị $\Psi$ lớn nhất khi dùng chiến thuật tối ưu. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá ${10}^{-6}$.

Ràng buộc

• $3\le n\le 100$
• $0\le p_i\le 1$

Ví dụ