[ABC008C] コイン

有 $n$ 枚硬币，每个硬币都有一个数。将这 $n$ 枚硬币随机打乱，并让每枚硬币正面朝上。之后，从左到右一次看每枚硬币，将它右边的所有它的倍数的硬币翻面。问：最后所朝上硬币的数量的期望值是多少？

[problemUrl]: https://atcoder.jp/contests/abc008/tasks/abc008_3 高橋君は裏表が区別できる $ N $ 枚のコインを持っている。コインの大きさは異なり、それぞれのコインには $ 1 $ つずつ正の整数が書かれている。 これらのコインを無作為に ($ N! $ 通りの組み合わせがすべて同じ確率で出てくるように) 一列に並べる。その後、以下の手順を実行する。 1. すべてのコインを表向きにする。 2. 左端のコインから順に、現在見ているコインよりも右側 (それ自身を除く) にあるコインのうち、現在見ているコインに書かれている整数の倍数が書かれているコインすべての裏表をひっくり返す。 高橋君はこの操作を終了した後に表を向いているコインの枚数の期待値が知りたい。 あなたは高橋くんの代わりに、期待値を計算するプログラムを作成してほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C_1 $ $ C_2 $ : $ C_N $ - $ 1 $ 行目には、コインの枚数を表す整数 $ N\ (1\ ≦\ N\ ≦\ 100) $ が与えられる。 - $ 2 $ 行目から $ N $ 行のうち $ i\ (1\ ≦\ i\ ≦\ N) $ 行目には、$ i $ 番目に大きいコインに書かれている整数 $ C_i\ (1\ ≦\ C_i\ ≦\ 10^9) $ が書かれている。

表を向いているコインの枚数の期待値を出力せよ。絶対誤差または相対誤差が $ 10^{-6} $ 以下であれば許容される。出力の末尾にも改行を入れること。

3
2
4
8

2.166666666667

4
5
5
5
5

2.000000000000

5
2
3
2
6
12

3.100000000000

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 8 $ を満たすデータセット $ 1 $ に正解した場合は、$ 99 $ 点が与えられる。 - 追加制約のないデータセット $ 2 $ に正解した場合は、さらに $ 1 $ 点が与えられ、合計で $ 100 $ 点が得られる。 ### Sample Explanation 1 コインには、サイズの小さい方から順にそれぞれ $ 2 $ , $ 4 $ , $ 8 $ という数が書かれています。例えば、$ 3! $ 通りの並べ方のうち、コインが大きさの昇順に並んでいる場合は、以下の手順が行われることになります。 1. 初期状態で、すべてのコインを表に向けるので、コインは左から順に、\\\[`表`, `表`, `表`\\\] となっています。 2. 次に、左から $ 2 $ 番目以降のコインの中で、$ 2 $ の倍数が書かれたコインを探します。左から $ 2 $ 番目のコインと左から $ 3 $ 番目のコインが該当するので、これらのコインを裏返します。その結果、コインは左から順に \\\[`表`, `裏`, `裏`\\\] となります。 3. 次に、左から $ 3 $ 番目以降のコインの中で、$ 4 $ の倍数が書かれたコインを探します。左から $ 3 $ 番目のコインのみが該当するので、このコインを裏返します。その結果、コインは左から順に \\\[`表`, `裏`, `表`\\\] となります。 コインの裏表は下図のように変化します。この図において、白いコインは表向きのコイン、黒いコインは裏向きのコインで表してあります。 !\[\](http://abc008.contest.atcoder.jp/img/abc/008/3-1.png)このように、$ 3!\ =\ 6 $ 通りの並べ方について、それぞれの並べ方での最終状態は下図のようになります。 !\[\](http://abc008.contest.atcoder.jp/img/abc/008/3-2.png)以上より期待値は $ 13/6\ =\ 2.16666666666... $ となります。 ### Sample Explanation 2 どのような順番で並べても、左から順に、\\\[`表`, `裏`, `表`, `裏`\\\] となります。