Bạn đang tham gia một trận đấu lockout. Luật chơi rất đơn giản: đây là cuộc thi 1v1, có $n$ bài toán với số điểm khác nhau được gán cho mỗi bài. Chỉ người đầu tiên nộp bài được chấp nhận (accepted) mới nhận được số điểm đó, ngay cả khi người kia chỉ chậm hơn 1 giây thì họ cũng không nhận được điểm nào. Để đơn giản, chúng ta sẽ không tính đến giới hạn thời gian hay chiến thắng sớm: trận đấu tiếp tục cho đến khi mỗi bài toán được giải bởi ít nhất một trong hai người tham gia.
Bạn khá giỏi, nhưng... bạn đang đối đầu với tourist. Đó là một thảm họa, tôi biết. Sẽ rất khó để giành chiến thắng nhưng bạn hy vọng giành được một vài điểm để giữ thể diện. Nếu bạn và tourist cùng làm một bài toán thì chắc chắn anh ấy sẽ thắng bạn. Nhưng nếu bạn chọn một bài toán khác thì đó là cơ hội của bạn! Bạn sẽ có thể giải bài toán này trước tourist! Nhưng sau đó anh ấy sẽ bước vào trạng thái "berserk" và giải tất cả các bài toán còn lại ngay lập tức. Một bài còn hơn không, phải không?
Hãy chính thức hóa quá trình này một chút. Mỗi lần, bạn và tourist có một số bài toán chưa giải để lựa chọn. Nếu không còn bài toán nào chưa giải, trò chơi kết thúc và bạn nhận được 0 điểm. Nếu không, cả bạn và tourist đều chọn một bài toán để làm, mà không biết người kia đã chọn bài nào. Nếu bạn chọn cùng một bài toán, tourist sẽ giải nó trước bạn và chúng ta quay lại trạng thái ban đầu với ít bài toán hơn. Ngược lại, bạn nhận được số điểm của bài toán bạn đã chọn, nhưng trò chơi kết thúc ngay lập tức vì tourist giải tất cả các bài toán còn lại ngay lập tức.
Bạn muốn tối đa hóa số điểm bạn nhận được, tourist muốn tối thiểu hóa nó. Kết quả kỳ vọng của trò chơi là bao nhiêu nếu cả bạn và tourist đều chơi tối ưu?
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 22$) — số lượng bài toán. Dòng thứ hai chứa $n$ số nguyên $a_i$ ($1 \le a_i \le 10^9$) — số điểm cho mỗi bài toán.
Dữ liệu ra
In ra một số — điểm số kỳ vọng của bạn. Câu trả lời của bạn được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-6}$. Chính thức hơn, gọi câu trả lời của bạn là $a$ và câu trả lời của giám khảo là $b$. Câu trả lời của bạn được chấp nhận khi và chỉ khi $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.
Ví dụ
Dữ liệu vào 1
2 6 7
Dữ liệu ra 1
3.2307692307692
Dữ liệu vào 2
3 1 1 1
Dữ liệu ra 2
0.8333333333333
Dữ liệu vào 3
11 1 2 3 4 5 6 7 8 9 10 11
Dữ liệu ra 3
9.4422713866103
Ghi chú
Lưu ý rằng trong ví dụ đầu tiên, tourist chắc chắn có thể thắng trận đấu bằng cách luôn chọn bài toán thứ hai, và chống lại chiến thuật này, bạn luôn có thể chọn bài toán thứ nhất và nhận được 6 điểm. Nhưng tourist sẽ chơi tối ưu để tối thiểu hóa điểm số kỳ vọng của bạn, điều này đôi khi có nghĩa là cho phép bạn thắng trận đấu.