Bob takes part in a traditional gift box lottery game held every year. In this game, there are an infinite number of identical gift boxes with the same content inside. Each box contains \(N\) gifts, labeled from \(1\) to \(N\), having values \(A_1, A_2, \dots, A_N\) respectively. The players know these values ahead of time.

A player must start out with a random gift box, pulling gifts from it randomly, one gift at a time. All gifts in the box have an equal chance to be pulled. The gift with label \(1\) is special: after you pull this gift, you gain the right to skip the remaining gifts in this box and move on to the next gift box. This right can be exercised whenever, as long as you are still pulling from the same box. Unless using the above special right, you must pull until the current box is empty before moving to the next box. Pulling the special gift from the next box will grant you the special right for the new box.

If Bob plays this game optimally, what would be the best value per pull he can get?

Input

• The first line of input contains one integer \(N\) (\(1 \le N < 20\)), the number of gifts per gift box.
• The following line contains \(N\) real numbers \(A_i\) (\(0 \le A_i \le 10^6\)), the value of each gift.

Output

• Output a single number, the best value per pull Bob can achieve if he plays optimally. The answer is considered correct if the precision error is less than \(10^{-5}\).

Example

2
0 1

0.5

2
1 0

0.6666666667

3
2 1 0

1.25

Nguồn: ICPC North 2021