Problem Description

Takahashi has $ N $ coins that can be distinguished by their heads and tails. The coins are of different sizes, and each coin has a positive integer written on it.

These coins are arranged randomly in a line (with all $ N! $ combinations equally likely). Then, the following procedure is executed:

1. All coins are flipped to show heads.
2. Starting from the leftmost coin, for each coin, flip all coins to the right of it (excluding itself) that have a multiple of the integer written on the current coin.

Takahashi wants to know the expected number of coins that will be heads up after this operation.

You are asked to create a program that calculates this expectation on behalf of Takahashi.

Input Format

The input is given from the standard input in the following format:

$ N $ $ C_1 $ $ C_2 $ : $ C_N $

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 100)$, representing the number of coins.
• The next $ N $ lines contain the integers $C_i\ (1\ ≦\ C_i\ ≦\ 10^9)$ written on the $ i $-th largest coin.

Output Format

Output the expected number of coins that will be heads up. The output will be accepted if the absolute or relative error is at most $ 10^{-6} $. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
2
4
8

Sample Output #1

2.166666666667

Sample Input #2

4
5
5
5
5

Sample Output #2

2.000000000000

Sample Input #3

5
2
3
2
6
12

Sample Output #3

3.100000000000

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N\ ≦\ 8$ correctly, you will be awarded $ 99 $ points.
• If you solve the dataset without additional constraints correctly, you will be awarded an additional $ 1 $ point, totaling $ 100 $ points.

Sample Explanation 1

The coins have the numbers $ 2 $, $ 4 $, and $ 8 $ written on them, in ascending order of size. For example, if the coins are arranged in ascending order of size, the following steps will occur:

1. Initially, all coins are heads up, so the coins are \[`heads`, `heads`, `heads`\].
2. Next, among the coins from the second position onwards, find the coins that have a multiple of $ 2 $. The second and third coins from the left are applicable, so these coins are flipped. The result is \[`heads`, `tails`, `tails`\].
3. Then, among the coins from the third position onwards, find the coins that have a multiple of $ 4 $. Only the third coin from the left is applicable, so this coin is flipped. The result is \[`heads`, `tails`, `heads`\].

The heads and tails of the coins change as shown in the diagram below, where white coins are heads up and black coins are tails up.

From this, the expected value is $13/6\ =\ 2.16666666666...$.

Sample Explanation 2

Regardless of the order in which the coins are arranged, they will always end up as \[`heads`, `tails`, `heads`, `tails`\].

见题面 Input 部分

见题面 Output 部分