题目描述

Alex 正在参与 BrMeast 的又一次视频拍摄，BrMeast 让 Alex 准备 25 万吨 TNT，但 Alex 没听清楚，于是他准备了 $n$ 个箱子，并将它们排成一排等待卡车。第 $i$ 个从左数的箱子重量为 $a_i$ 吨。

所有 Alex 要用的卡车每辆都能装下相同数量的箱子，记为 $k$。装载过程如下：

• 前 $k$ 个箱子装进第一辆卡车，
• 接下来的 $k$ 个箱子装进第二辆卡车，
• 以此类推，
• 最后 $k$ 个箱子装进第 $\frac{n}{k}$ 辆卡车。

装载完成后，每辆卡车必须正好装 $k$ 个箱子。换句话说，如果在某种情况下无法让每辆卡车都装满 $k$ 个箱子，则该 $k$ 的装载方式不可行。

Alex 不喜欢公平，所以他希望任意两辆卡车所装箱子的总重量的最大绝对差尽可能大。如果只有一辆卡车，这个值为 $0$。

Alex 人脉广泛，所以对于每个 $1 \leq k \leq n$，他都能找到一家公司的卡车能正好装下 $k$ 个箱子。请输出任意两辆卡车所装箱子总重量的最大绝对差的最大值。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 150\,000$），表示箱子的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示每个箱子的重量。

保证所有测试用例中 $n$ 的总和不超过 $150\,000$。

输出格式

对于每个测试用例，输出一个整数，表示题目的答案。

说明/提示

在第一个样例中，我们应选择两辆卡车，第一辆只装第一个箱子，第二辆只装第二个箱子。

在第二个样例中，应选择六辆卡车，最大值为 $10$，最小值为 $1$，答案为 $10 - 1 = 9$。

在第三个样例中，无论选择哪种 $k$，每辆卡车装箱子的总重量都相同，所以答案为 $0$。

由 ChatGPT 4.1 翻译

样例

5
2
1 2
6
10 2 3 6 1 3
4
1000000000 1000000000 1000000000 1000000000
15
60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294
8
19957 69913 37531 96991 57838 21008 14207 19198

1
9
0
189114
112141