C. Socks Drying
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Gleb has socks of $$$n$$$ distinct colors. In particular, he owns $$$a_i$$$ pairs of socks of color $$$i$$$. He wears these pairs one after the other till there are no more clean pairs of socks left, then it is time for The Great Wash.

Gleb puts all of his socks into a washing machine with a drying option and waits for an two-three hours. Now, the worst part begins. Gleb needs to assemble socks in pairs again. To simplify the process we assume that all socks of the same color are indistinguishable. In other words, any two socks of the same color can form a pair. Obviously, Gleb never forms a pair of socks from two of distinct color.

Gleb performs the following process. We denote the set of all socks inside the washing machine as $$$A$$$ and the set of all socks that haven't been matched yet and lie near Gleb as $$$B$$$.

  1. Gleb puts his hand into a washing machine and checks whether there are any socks left in $$$A$$$. If there are none, the process finishes. Otherwise, he puts out one random sock (with equal probabilities for all socks in $$$A$$$), we denote this sock as $$$x$$$. This is a single action that takes exactly one second.
  2. He then tries to find a pair for this sock among all socks with no pair already extracted out of the washing machine and lie near him, i.e. all socks in set $$$B$$$.
  3. Gleb considers all socks of $$$B$$$ in random order. All orders are equiprobable. It takes exactly one second to consider one sock from $$$B$$$. If the sock $$$x$$$ matches the sock just extracted from $$$A$$$ by color, they form a pair and this step finishes.
  4. If all socks from $$$B$$$ were considered and no match for $$$x$$$ was found, Gleb puts $$$x$$$ in the heap of unpaired socks. In other words sock $$$x$$$ goes to set $$$B$$$.
  5. Gleb goes back to step one.

While waiting for wash-and-dry cycle to finish Gleb wonders, what is the expected time the process described above will take? The last time he took part in a programming competition was several years ago, so he needs your help to find out the answer.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — the number of distinct colors of socks Gleb possesses.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 5$$$), the $$$i$$$-th of them denoting the number of pairs of socks of color $$$i$$$ in Gleb's wardrobe.

Output

Print one real value — the expected number of seconds it will take Gleb to complete the whole process if he follows the steps given. Your answer will be accepted if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
1
1
Output
3.000000000
Input
1
3
Output
9.000000000
Input
2
1 1
Output
7.000000000
Input
3
3 2 2
Output
29.571428571