CF1884E Hard Design

给定一个整数数组 $b_0, b_1, \ldots, b_{n-1}$，你的目标是使所有元素都相等。为此，你可以进行如下操作若干次（也可以为零次）： - 选择一对下标 $0 \le l \le r \le n-1$，然后对于每个 $l \le i \le r$，将 $b_i$ 增加 $1$（即将 $b_i$ 替换为 $b_i + 1$）。 - 每执行一次这样的操作，你会获得 $(r - l + 1)^2$ 个金币。 定义 $f(b)$ 为一个整数对 $(cnt, cost)$，其中 $cnt$ 表示将数组所有元素变为相等所需的最少操作次数，$cost$ 表示在所有能用 $cnt$ 次操作完成目标的方案中，能获得的最大金币总数。换句话说，首先你需要最小化操作次数 $cnt$，在此基础上最大化获得的金币总数 $cost$。 现在给定一个整数数组 $a_0, a_1, \ldots, a_{n-1}$。请你对于 $a$ 的所有循环移位，求出 $f$ 的值。 具体来说，对于每个 $0 \le i \le n-1$，你需要执行以下操作： - 令 $c_j = a_{(j + i) \bmod n}$，其中 $0 \le j \le n-1$。 - 求出 $f(c)$。由于 $cost$ 可能非常大，输出其对 $10^9 + 7$ 取模的结果。 请注意，在确定了最小操作次数 $cnt$ 后，你需要最大化金币总数 $cost$，而不是最大化其模 $10^9 + 7$ 的余数。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试数据组数。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^6$）。 每组测试数据的第二行包含 $n$ 个整数 $a_0, a_1, \ldots, a_{n-1}$（$1 \le a_i \le 10^9$）。 保证所有测试数据中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，对于每个 $0 \le i \le n-1$，输出数组 $a$ 的第 $i$ 次循环移位对应的 $f$ 值：先输出 $cnt$（最小操作次数），再输出 $cost$（最大金币总数，对 $10^9 + 7$ 取模）。

在第一个测试点中，只有一个循环移位，即 $[1]$，所有元素已经相等。 在第二个测试点中，你需要对三个数组分别求解： 1. $f([1, 3, 2]) = (3, 3)$。 2. $f([3, 2, 1]) = (2, 5)$。 3. $f([2, 1, 3]) = (2, 5)$。 以 $[2, 1, 3]$ 为例。为了使所有元素相等，可以第一次选择 $l = 1$，$r = 1$，得到 $[2, 2, 3]$。第二次选择 $l = 0$，$r = 1$，得到 $[3, 3, 3]$。共用了 $2$ 次操作，获得的金币总数为 $1^2 + 2^2 = 5$。 由 ChatGPT 4.1 翻译