Blindfold Nim

Time limit2sMemory limit512 MB

Summary

Each stack size is uniform on [0, a_i]; compute the probability that the first player wins a game of Nim with hidden positions where a player who overshoots a stack loses at once.

Level: Hard9 of 10
Topics: Dynamic programming, Combinatorics, Bit manipulation, Game theory
Solved: No attempts yet

Problem

Sprague and Grundy have been playing the game of Nim. They put $n$ stacks of coins on a table and move alternately. On each turn a player picks one stack and removes any positive number of coins from it. A player who cannot make a valid move loses.

They quickly worked out the optimal strategy, so now they want something more interesting: they decide to play blindfolded. All they know is that the initial number of coins in the $i$ -th stack is drawn uniformly at random from the integers in $[0, a_i]$ , every integer in that range being equally likely, and the stacks are drawn independently. A player loses immediately if he tries to take more coins from a stack than it currently holds. In particular, if a player is certain that every stack is empty, he must still move and therefore loses. Sprague moves first. Assuming both players play optimally and can see each other's moves, what is the probability that Sprague wins?

Input

The first line contains an integer $n$ ( $1 \le n \le 10^6$ ), the number of stacks. The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ . The sum of these integers does not exceed $10^6$ .

Output

Print a single real number: the probability that Sprague wins, rounded to exactly $9$ digits after the decimal point.

Examples4

Example 1
Input
```
3
1 1 1
```
Expected output
```
0.375000000
```
Example 2
Input
```
1
1
```
Expected output
```
0.500000000
```
Example 3
Input
```
1
2
```
Expected output
```
0.333333333
```
Example 4
Input
```
2
2 3
```
Expected output
```
0.500000000
```