\(N\) (\(1 \leq N \leq 10^5\)) коров Фермера Джона выстроены в ряд так, что
\(i\)-ая корова в этому ряду имеет уровень голода \(h_i\) (\(0 \leq h_i \leq 10^9\)).
Поскольку коровы - социальные животные и хотят есть вместе, единственный способ
уменьшить уровень голода его коров - выбрать двух соседних коров с номерами
\(i\) и \(i+1\) и скормить каждой из них по мешку кукурузы, чтобы уменьшить уровень
голода каждой из них на один.
ФД хочет накормить своих коров так, чтобы все имели один и тот же некоторый
не отрицательный уровень голода. Помогите ФД определить минимальное количество
мешков кукурузы, которое ему потребуется, или -1, если это сделать невозможно.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Каждый ввод состоит из нескольких независимых тестов, каждый из которых
нужно решить правильно, чтобы решить полностью входной тест. Первая строка
содержит \(T\) (\(1\le T\le 100\)) - количество тестов на вводе. Каждый тест описывается
парой строк. Первая строка в паре содержит \(N\), а вторая - \(h_1,h_2,\ldots,h_N\).
Гарантируется, что сумма всех \(N\) в тесте не превысит \(10^5\). Значения \(N\)
могут различаться внутри ввода.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\) строк, по одной для каждого теста на вводе.
Заметим что требуется использовать 64-битное целое для ответа
(например "long long" в C/C++)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9
|
14
16
-1
-1
-1
|