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

#格式#
##输入格式##
先一行中有一个整数n (1&lt=n&lt8)
然后下一行中有n个整数，表示原数列
数据不超过15组

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

#样例1#
##样例输入1##

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

##样例输出1##

1.0000
4.0667
0.0000
5.6667

#限制#
1000ms
32768KB

#提示#

#来源#
DK