CF1899B.250 Thousand Tons of TNT

Alex is participating in the filming of another video of BrMeast, and BrMeast asked Alex to prepare 250 thousand tons of TNT, but Alex didn't hear him well, so he prepared $n$ boxes and arranged them in a row waiting for trucks. The $i$-th box from the left weighs $a_i$ tons.

All trucks that Alex is going to use hold the same number of boxes, denoted by $k$. Loading happens the following way:

• The first $k$ boxes goes to the first truck,
• The second $k$ boxes goes to the second truck,
• $\dotsb$
• The last $k$ boxes goes to the $\frac{n}{k}$-th truck.

Upon loading is completed, each truck must have exactly $k$ boxes. In other words, if at some point it is not possible to load exactly $k$ boxes into the truck, then the loading option with that $k$ is not possible.

Alex hates justice, so he wants the maximum absolute difference between the total weights of two trucks to be as great as possible. If there is only one truck, this value is $0$.

Alex has quite a lot of connections, so for every $1 \leq k \leq n$, he can find a company such that each of its trucks can hold exactly $k$ boxes. Print the maximum absolute difference between the total weights of any two trucks.

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

Alex 将使用的全部卡车每辆装载的箱子数量相同，记为 $k$。装运过程如下：

• 前 $k$ 个箱子装入第一辆卡车，
• 接下来的 $k$ 个箱子装入第二辆卡车，
• $\dotsb$
• 最后 $k$ 个箱子装入第 $\frac{n}{k}$ 辆卡车。

装运完成后，每辆卡车必须恰好装有 $k$ 个箱子。换言之，若在某一步无法恰好装入 $k$ 个箱子，则该 $k$ 值对应的装运方案不可行。

Alex 讨厌公平，因此他希望任意两辆卡车总重量之差的绝对值尽可能大。若仅有一辆卡车，则该值为 $0$。

Alex 人脉很广，因此对每个满足 $1 \leq k \leq n$ 的 $k$，他都能找到一家公司，其每辆卡车恰好可装载 $k$ 个箱子。请输出所有可行 $k$ 值中，任意两辆卡车总重量之差的绝对值的最大值。

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 150\,000$) — the number of boxes.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the weights of the boxes.

It is guaranteed that the sum of $n$ for all test cases does not exceed $150\,000$.

第一行包含一个整数 $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$。

For each test case, print a single integer — the answer to the problem.

对于每个测试用例，输出一个整数——即该问题的答案。

In the first case, we should pick two trucks, so the first one will have only the first box, and the second one will have only the second box.

In the second case, we should pick six trucks, so the maximum will be $10$, the minimum will be $1$, and the answer is $10 - 1 = 9$.

In the third case, for any possible $k$, the trucks will have the same total weight of boxes, so the answer is $0$.

第一种情况，我们需要选择两辆卡车，因此第一辆卡车只装载第一个箱子，第二辆卡车只装载第二个箱子。

第二种情况，我们需要选择六辆卡车，此时最大总重量为 $10$，最小总重量为 $1$，答案为 $10 - 1 = 9$。

第三种情况，对于任意可能的 $k$，每辆卡车所装载的箱子总重量均相同，因此答案为 $0$。