E. Сложная конструкция
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим массив целых чисел $$$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}$$$. Найдите значение $$$f$$$ для всех циклических сдвигов массива $$$a$$$.

Формально, для каждого $$$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$$$ выведите значение $$$f$$$ для $$$i$$$-го циклического сдвига массива $$$a$$$: сначала выведите $$$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
Примечание

В первом наборе входных данных есть всего один циклический сдвиг, задающийся массивом $$$[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$$$.