310773: CF1884E. Hard Design

E. Hard Designtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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)$.

Input

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$.

Output

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$.

ExampleInput

5
1
1
3
1 3 2
5
3 2 4 5 1
8
6 5 6 4 2 6 2 2
4
10 10 10 10

Output

0 0
3 3
2 5
2 5
7 18
7 16
6 22
5 28
5 28
9 27
9 27
9 27
9 27
11 23
9 27
9 27
13 19
0 0
0 0
0 0
0 0

Note

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$.

题目大意：

给定一个整数数组 $ b_0, b_1, \ldots, b_{n-1} $，目标是使所有元素相等。可以通过以下操作来实现，可以执行多次（可能为零次）：

1. 选择一对索引 $ 0 \le l \le r \le n-1 $，然后对于每个 $ l \le i \le r $，将 $ b_i $ 增加 1（即用 $ b_i + 1 $ 替换 $ b_i $）。
2. 执行此操作后，获得 $ (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 $，执行以下操作：

1. 令 $ c_j = a_{(j + i) \mod n} $ 对于每个 $ 0 \le j \le n-1 $。
2. 找到 $ 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 $ 的结果。

示例：

输入：
```
5
1
1
3
1 3 2
5
3 2 4 5 1
8
6 5 6 4 2 6 2 2
4
10 10 10 10
```

输出：
```
0 0
3 3
2 5
2 5
7 18
7 16
6 22
5 28
5 28
9 27
9 27
9 27
9 27
11 23
9 27
9 27
13 19
0 0
0 0
0 0
0 0
```题目大意： 给定一个整数数组 $ b_0, b_1, \ldots, b_{n-1} $，目标是使所有元素相等。可以通过以下操作来实现，可以执行多次（可能为零次）： 1. 选择一对索引 $ 0 \le l \le r \le n-1 $，然后对于每个 $ l \le i \le r $，将 $ b_i $ 增加 1（即用 $ b_i + 1 $ 替换 $ b_i $）。 2. 执行此操作后，获得 $ (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 $，执行以下操作： 1. 令 $ c_j = a_{(j + i) \mod n} $ 对于每个 $ 0 \le j \le n-1 $。 2. 找到 $ 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 $ 的结果。 示例： 输入： ``` 5 1 1 3 1 3 2 5 3 2 4 5 1 8 6 5 6 4 2 6 2 2 4 10 10 10 10 ``` 输出： ``` 0 0 3 3 2 5 2 5 7 18 7 16 6 22 5 28 5 28 9 27 9 27 9 27 9 27 11 23 9 27 9 27 13 19 0 0 0 0 0 0 0 0 ```