Description

现在要将一个由前n个正整数构成的数组a排成升序，可以通过一系列的交换操作来完成排序。每次交换操作交换的两个数的下标假设为i和j，则一个合法的交换为ia[j]。每次交换时，等可能的随机选择一个合法的交换操作进行交换。求将数列a排成升序所进行交换次数的期望。

Input

先一行中有一个整数n (1<=n<8) 然后下一行中有n个整数，表示原数列 数据不超过15组

Output

每组数据输出一行期望交换次数，四舍五入至小数点后第四位。

Sample

Input

3
1 3 2
4
4 3 2 1
1
1
6
2 5 1 6 3 4

Output

1.0000
4.0667
0.0000
5.6667

Source: DK