408849: GYM103348 K Antony and Cleopatra

Egypt's Queen, Cleopatra, has seduced Mark Antony, one of the triumvirs of the Roman Republic. Rome's domestic problems have put the empire in dire straits, but Cleopatra begs Antony to stay with her in Alexandria. Antony proposes that they play a parlor game to decide if he stays; if Cleopatra wins, he will stay, but otherwise, Antony will leave.

The game is played upon a table with $$$N$$$ card-shaped spaces, and every space has a positive integer at most $$$100$$$ engraved in it. Each player is initially dealt $$$N$$$ cards, and a single random integer in the range $$$[1, 10^{100}]$$$ is written on every card. Cleopatra will begin by viewing the number engraved on each space, and then will place exactly one card into every space on the table. Antony will then view the numbers and positions of Cleopatra's cards on the table in addition to the engraved numbers, and place his cards in the same fashion as Cleopatra. For each space, the player with the higher number on their card within that space receives points equivalent to the number engraved in the space. If both players place the same number on a space, no one gets any points.

Given that Antony plays optimally, Cleopatra would like to know the expected number of points she will score if she uses the highest scoring strategy to assess the likelihood of Antony staying. Can you help the Queen of Egypt?

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 100$$$) as described above. The second line of input contains $$$N$$$ space-separated positive integers at most $$$100$$$ that denote the numbers engraved into the spaces on the playing table.

Print a single number representing the expected number of points Cleopatra will score in the game. Answers within $$$10^{-6}$$$ of the true expectation will be accepted.

2
1 2

1.3333333333

3
5 7 11

9.2000000000