Жан, уставший после контеста, дал единственную задачу, которую не решил во время контеста, своему другу, Сунгату. Однако и он не смог решить, поэтому мы просим вас попробовать решить эту задачу.
Дан массив \(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)\).
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное возможное значение \(\max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)\).
Примечание
В третьем наборе входных данных можно дважды проделать операцию с \(i = 1\).
После этого массив \(a = [2, 3, 2, 3]\), \(\max(2, 3, 2, 3) - \min(2, 3, 2, 3) = 3 - 2 = 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|