CF1884E.Hard Design

Consider an array of integers $b_0, b_1, \ldots, b_{n-1}$. Your goal is to make all its elements equal. To do so, you can perform the following operation several (possibly, zero) times:

• Pick a pair of indices $0 \le l \le r \le n-1$, then for each $l \le i \le r$ increase $b_i$ by $1$ (i. e. replace $b_i$ with $b_i + 1$).
• After performing this operation you receive $(r - l + 1)^2$ coins.

The value $f(b)$ is defined as a pair of integers $(cnt, cost)$, where $cnt$ is the smallest number of operations required to make all elements of the array equal, and $cost$ is the largest total number of coins you can receive among all possible ways to make all elements equal within $cnt$ operations. In other words, first, you need to minimize the number of operations, second, you need to maximize the total number of coins you receive.

You are given an array of integers $a_0, a_1, \ldots, a_{n-1}$. Please, find the value of $f$ for all cyclic shifts of $a$.

Formally, for each $0 \le i \le n-1$ you need to do the following:

• Let $c_j = a_{(j + i) \pmod{n}}$ for each $0 \le j \le n-1$.
• Find $f(c)$. Since $cost$ can be very large, output it modulo $(10^9 + 7)$.

Please note that under a fixed $cnt$ you need to maximize the total number of coins $cost$, not its remainder modulo $(10^9 + 7)$.

考虑一个整数数组 $b_0, b_1, \ldots, b_{n-1}$。你的目标是使该数组所有元素相等。为此，你可以执行以下操作若干次（可能为零次）：

• 选择一对下标 $0 \le l \le r \le n-1$，然后对每个满足 $l \le i \le r$ 的 $i$，将 $b_i$ 增加 $1$（即用 $b_i + 1$ 替换 $b_i$）；
• 执行该操作后，你将获得 $(r - l + 1)^2$ 枚金币。

函数 $f(b)$ 定义为一个二元组 $(cnt, cost)$，其中 $cnt$ 是使数组所有元素相等所需的最少操作次数，而 $cost$ 是在恰好使用 $cnt$ 次操作的所有可行方案中，所能获得的金币总数的最大值。换言之，首先需最小化操作次数，其次在满足该最小操作次数的前提下，最大化所获金币总数。

现给定一个整数数组 $a_0, a_1, \ldots, a_{n-1}$。请对数组 $a$ 的所有循环移位，分别求出其对应的 $f$ 值。

形式化地，对每个 $0 \le i \le n-1$，你需要执行以下步骤：

• 对每个 $0 \le j \le n-1$，令 $c_j = a_{(j + i) \pmod{n}}$；
• 求出 $f(c)$。由于 $cost$ 可能非常大，请将其对 $(10^9 + 7)$ 取模后输出。

请注意：在固定 $cnt$ 的前提下，你需要最大化金币总数 $cost$，而非其对 $(10^9 + 7)$ 取模后的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$).

The second line of each test case contains $n$ integers $a_0, a_1, \ldots, a_{n-1}$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, for each $0 \le i \le n-1$ output the value of $f$ for the $i$-th cyclic shift of array $a$: first, output $cnt$ (the minimum number of operations), then output $cost$ (the maximum number of coins these operations can give) modulo $10^9 + 7$.

对于每个测试用例，对每个 $0 \le i \le n-1$，输出数组 $a$ 的第 $i$ 个循环移位对应的函数 $f$ 的值：首先输出 $cnt$（最少操作次数），然后输出 $cost$（这些操作所能获得的最大金币数）对 $10^9 + 7$ 取模的结果。

In the first test case, there is only one cycle shift, which is equal to $[1]$, and all its elements are already equal.

In the second test case, you need to find the answer for three arrays:

1. $f([1, 3, 2]) = (3, 3)$.
2. $f([3, 2, 1]) = (2, 5)$.
3. $f([2, 1, 3]) = (2, 5)$.

Consider the case of $[2, 1, 3]$. To make all elements equal, we can pick $l = 1$ and $r = 1$ on the first operation, which results in $[2, 2, 3]$. On the second operation we can pick $l = 0$ and $r = 1$, which results in $[3, 3, 3]$. We have used $2$ operations, and the total number of coins received is $1^2 + 2^2 = 5$.

在第一个测试用例中，只有一个循环移位，即 $[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$。