Hard Design
Contest: Codeforces Round 904 (Div. 2)
Difficulty rating: 2800
Tags: greedy, implementation, math

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example 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

Editorial:
Let's learn how to solve a problem for a given array. Notice that we want to make all elements equal to the maximum value in the array. For convenience, let's solve a similar problem that is easier to implement. We'll create an array $$$b_i = \max(a) - a_i$$$. Then, instead of performing an addition operation, we'll perform a subtraction operation by $$$-1$$$ on a range, aiming to make all elements of the array equal to $$$0$$$.
Let $$$pos$$$ be the position of the minimum element in the array $$$b$$$. We can apply the operation $$$b_{pos}$$$ times on the entire array, and then recursively solve the problem for the left and right parts relative to the position $$$pos$$$. However, this doesn't help us solve the problem for all shifts. Let's find the nearest element less than or equal to each element on the left (denoted as $$$l_i$$$) and the nearest element less than each element on the right (denoted as $$$r_i$$$) - this can be done using linear algorithms. Then, we can observe that when we consider the subarray $$$l_i + 1 \ldots r_i - 1$$$ in our recursive solution, we add to the answer a value equal to $$$b_i - \max(b_{l_i}, b_{r_i})$$$. We have found a solution to the problem in $$$O(n)$$$ time for a fixed array $$$a$$$.
If we consider all shifts of the array, the nearest elements on the left/right either remain unchanged or simply do not exist, in which case we consider their values to be $$$0$$$. Therefore, if we fix the position $$$i$$$ (want to determine how much it affects the answer for each position in the array), we have three shift ranges for which we can add different values. Hence, we have $$$O(n)$$$ ranges on which we need to add certain values. Since we don't have to make these additions immediately, we can create an array $$$add_i$$$ - the value that needs to be added to all elements starting from position $$$i$$$. Then, adding the number $$$x$$$ on the range $$$l \ldots r$$$ changes this array as follows: $$$add_l = add_l + x$$$, $$$add_{r + 1} = add_{r + 1} - x$$$. The answer to the problem is $$$ans_i = \sum\limits_{j=1}^i add_i$$$. This subproblem can be solved in $$$O(n)$$$ time.
Next, we need to learn how to calculate the total cost. The approach will be similar, but now we need to add a more complex function. If both nearest elements are within a shift range, we will add $$$(r_i - l_i - 1)^2 \cdot (b_i - \max(b_{l_i}, b_{r_i})$$$ - a fixed number. If there is no nearest element on the left/right, we will add a value of the form $$$(r_i - s + 1)^2 \cdot (b_i - b_{r_i})$$$ or $$$(s + n - i + 1)^2 \cdot (b_i - b_{l_i})$$$, where $$$s$$$ is the index of the start of the shift position. Both cases can be solved similarly. If we expand the brackets, we get an expression of the form $$$a \cdot s^2 + b \cdot s + c$$$, where $$$a, b, c$$$ are known coefficients. Let's represent the answer for a fixed shift in this form, and we need to find the value of each coefficient, which is simply adding a fixed number on a range, as we discussed in the previous paragraph. This can also be solved in $$$O(n)$$$ time.