Рассмотрим массив целых чисел \(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)\).
Выходные данные
Для каждого набора входных данных для каждого \(0 \le i \le n-1\) выведите значение \(f\) для \(i\)-го циклического сдвига массива \(a\): сначала выведите \(cnt\) (наименьшее количество операций), затем \(cost\) (наибольшее суммарное число монет, которое могут принести эти операции) по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных есть всего один циклический сдвиг, задающийся массивом \([1]\), и в нем все элементы уже равны.
Во втором наборе входных данных нужно найти ответ на трех массивах:
- \(f([1, 3, 2]) = (3, 3)\).
- \(f([3, 2, 1]) = (2, 5)\).
- \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|