D. Минимизировать разницу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Жан, уставший после контеста, дал единственную задачу, которую не решил во время контеста, своему другу, Сунгату. Однако и он не смог решить, поэтому мы просим вас попробовать решить эту задачу.

Дан массив $$$a_1, a_2, \ldots, a_n$$$ длины $$$n$$$. Мы можем выполнить с массивом любое количество (возможно, ноль) операций.

За одну операцию мы выбираем позицию $$$i$$$ ($$$1 \leq i \leq n - 1$$$), и выполняется следующее действие:

  • $$$a_i := a_i - 1$$$, и $$$a_{i+1} := a_{i+1} + 1$$$.

Найдите минимальное возможное значение $$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{12}$$$).

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимальное возможное значение $$$\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)$$$.

Пример
Входные данные
5
1
1
3
1 2 3
4
4 1 2 3
4
4 2 3 1
5
5 14 4 10 2
Выходные данные
0
2
1
1
3
Примечание

В третьем наборе входных данных можно дважды проделать операцию с $$$i = 1$$$.

После этого массив $$$a = [2, 3, 2, 3]$$$, $$$\max(2, 3, 2, 3) - \min(2, 3, 2, 3) = 3 - 2 = 1$$$.