题目描述

1tthinking 特别喜欢玩 guitar hero。

现在有 $n$ 首歌在这个游戏中，他们被标为 $1$ 到 $n$。游戏会随机把歌曲分组 $p$。

更详细的说，对于 $p_{1\cdots n}$，游戏会在第 $i$ 首之后播放第 $p_{i}$ 首。因此这 $n$ 首歌会形成几个循环来播放。举个例子，如果 $n = 3,p = \{2, 1, 3\}$，我们得到了 $\{1, 2\}$ 和 $\{3\}$ 两个循环。

每首歌有一个积分值，1thinking 特别喜欢玩 Queen 的 Another One Bites The Dust，每次他一定会玩这首歌。现在 1thinking 知道这首歌是积分值 第二大 的歌曲。他想知道他喜欢的歌所在的循环的分数和。

现在给出 $n$ 首歌的难度值，求 1tthinking 游戏一次所获得的期望积分和是多少？

举个例子，当前有三首歌，积分为 $1,2,3$。1tthinking 总是会选择积分为 $2$ 的歌曲。

一共可能的排列有 $6$ 种： $\{1, 2, 3\}, \{1, 3, 2\}, \{2, 1, 3\}, \{2, 3, 1\}, \{3, 1, 2\} , \{3, 2, 1\}$。1tthinking 分别会等概率选择 $\{2\}, \{2, 3\}, \{1, 2\}, \{1, 2, 3\}, \{1, 2, 3\}, \{2\}$ 获得 $2, 5, 3, 6, 6, 2$ 分。平均可以获得 $\frac{(2 + 5 + 3 + 6 + 6 + 2)} 6 = \frac{24 } 6 = 4.0000$ 分。

输入格式

第一行一个整数 $T$ 表示数据的组数。

对于每组数据，第一行一个整数 $n$，表示排列的长度。

第二行，$n$ 个整数 $v_{1\cdots n}$ 表示每首歌的积分值。

输出格式

对于每组数据，输出一个浮点数，表示期望积分，精确到 $10^{-6}$。

1
3
1 2 3

4.000000

数据规模与约定

对于 $100\%$ 的数据，$2\leq n\leq 50$，$0\leq v_i\leq 2^{31}$。