M. 炫酷魔法

传统题

2000ms

1024MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

小 S 有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$ 。他拥有一种炫酷魔法，可以将这个序列划分为连续的 $k$ 段，每一段获得的魔法值为这一段中所有数的最大公因数。

小 S 需要使用恰好一次炫酷魔法，他希望通过选择合适的划分方式，使得这 $k$ 个魔法值的算术平均数尽可能大。请计算最大的可能值。

形式化地，给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \ldots, a_n$ ，你需要选择一个整数 $k$ $(1 \le k \le n)$ ，并将整个序列划分为 $k$ 个连续的非空子段：

$$[a_1, \ldots, a_{p_1}],\ [a_{p_1 + 1}, \ldots, a_{p_2}],\ \ldots,\ [a_{p_{k-1} + 1}, \ldots, a_n] $$

其中 $p_0 = 1 \le p_1 < p_2 < \cdots < p_{k-1} < n = p_k$ 。

最大化：

$$\frac{1}{k} \sum_{i=1}^{k} \gcd(a_{p_{i-1}+1}, a_{p_{i-1}+2}, \ldots, a_{p_i}). $$

输入包含多组数据。

首先输入一行一个整数 $T$ ( $1 \leq T \leq 10^4$ )，表示数据的组数。

对于每组数据，首先输入一行一个整数 $n$ ( $1 \leq n \leq 2 \cdot 10^5$ )，表示给定序列的长度。

接下来输入一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^6$ )，表示给定的序列。

保证对于一个测试点的所有数据， $n$ 的和不超过 $2 \cdot 10^5$ 。

对于每组数据，输出一行一个实数，表示最大的可能值。

当且仅当你的输出与答案的绝对误差或相对误差不超过 $10^{-4}$ 时，你的答案会被判定为正确。

7.000000000000
5.800000000000
4.000000000000
7.000000000000

在第一组数据中，将给定的序列划分为 $[6, 6], [8]$ 是最优的。这两个子段的魔法值分别为 $6$ , $8$ 。所有子段的魔法值的\textbf{算术平均数}为 $7$ 。

在第二组数据中，可以证明，将给定的序列划分为 $[1], [6], [12], [6], [4]$ 是最优的。