考虑一个整数数组 $$$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$$$ 操作中使所有元素相等所需的所有可能方法中您可以获得的最大硬币总数。换句话说,首先,你需要最小化操作次数,其次,你需要最大化你收到的硬币总数。
给定一个整数数组 $$$a_0, a_1, \ldots, a_{n-1}$$$。请找出 $$$a$$$ 的所有循环移位的 $$$f$$$ 的值。
正式来说,对于每个 $$$0 \le i \le n-1$$$ 您需要执行以下操作:
- 让 $$$c_j = a_{(j + i) \pmod{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
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
输出 #1
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
注意
在第一个测试用例中,只有一个循环移位,它等于$$$[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$$$。