SP19293 WPC5E - Galaxy distances

在宇宙中，每个星系 $i$ 都被指定了一个独特的位置 $A(i)$。已知任意两个星系之间的距离计算公式为：$Dist(i, j) = (|i^2 - j^2| + |A(i)^2 - A(j)^2|)$。 为了举办活动，选择了一个星系作为主办地点，其他所有星系需要前往参加。为了这些星系的交通和活动参加，组织者需要支付相关费用。组织者想知道，他们可能需要支付的最大交通费用是多少。 请你帮忙计算并找出**最大**的 $Dist(i, j)$ 值。

第一行输入一个整数 $T$，表示测试用例的总数。 每个测试用例包含两行。第一行是一个整数 $n$，表示星系的数量（从 1 到 $n$ 依次编号）。 第二行是 $n$ 个用空格分隔的整数，代表每个星系的位置 $A(i)$，其中 $1 \le i \le n$。

对于每个测试用例，输出一行，表示该测试用例中的最大距离。

- 测试用例的数量 $1 \le T \le 10$ - 星系的数量 $2 \le n \le 10^5$ - 星系的位置 $1 \le A(i) \le 10^9$ **时间限制**：2 秒 **样例输入**： ``` 1 2 4 3 ``` **样例输出**： ``` 10 ``` **解释**：在这个例子中，当 $i=1$ 和 $j=2$ 时，距离 $Dist(i, j)$ 达到了最大值。 **本翻译由 AI 自动生成**