J - ボール 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

N 個のものがある。i 番目のものは座標 x_i におかれている。すぬけ君が、座標 x の点を目指してボールを投げると x-1, x, x+1 のうちのいずれかに 1/3 ずつの確率で飛んでいき、そこに物がおいてあった場合は倒れる。最適な戦略でボールを投げたとき、すべての物を倒すのに必要なボールを投げる回数の期待値を求めよ。

追記 : ボールを投げる場所は、前に投げたボールの飛んだ場所を見た後に決めることができる。

Constraints

  • 1 ≤ N ≤ 16
  • 0 ≤ x_i ≤ 15
  • x_i are pairwise distinct.

Input Format

入力は以下の形式で標準入力から与えられる。
N
x_1 ... x_N

Output Format

答えを一行に出力せよ。絶対誤差が 10^{-6} 以下のとき正当と判定される。

Sample Input 1

2
0 2

Sample Output 1

4.500000000
座標 1 に向かってボールを投げ続けるのがよい。

Sample Input 2

5
1 3 4 2 5

Sample Output 2

8.986111111