Засуха высушила траву Farmer John. После часов отчаяния и размышлений он придумал купить кукурузу любимым коровам.

$N$ коров ($1\le N\le10^5$) в ряд, голод $i$ равен $h_i$ ($0\le h_i\le10^9$). Общительные коровы едят только вместе: единственный способ — дать соседям $i,i+1$ по мешку, уменьшив голод каждой на один.

Нужно сделать голод всех равным и неотрицательным. Найдите минимум мешков либо -1, если невозможно.

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

Несколько независимых тестов надо решить все правильно. Сначала $T$ ($1\le T\le100$), затем по две строки: $N$ и $h_1,h_2,\ldots,h_N$. Сумма $N$ не более $10^5$, значения $N$ могут различаться.

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

$T$ строк, по одной на тест.

Большие значения могут требовать 64-битных целых, например C/C++ long long.

Примеры

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

5
3
8 10 5
6
4 6 4 4 6 4
3
0 1 0
2
1 2
3
10 9 9

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

14
16
-1
-1
-1

Примечание

В первом дать 2,3 по два мешка, затем 1,2 по пять, у всех голод 3.

Во втором дать 1,2 по два, 2,3 по два, 4,5 по два и 5,6 по два, голод всех 2.

В остальных выровнять голод невозможно.

Подзадачи

• Все тесты входа 2: $N\le3$, $h_i\le100$.
• Все тесты входов 3–8: $N\le100$, $h_i\le100$.
• Все тесты входов 9–14: $N\le100$.
• Вход 15 без дополнительных ограничений.

Кроме того, в 3–5 и 9–11 $N$ всегда чётно, в 6–8 и 12–14 всегда нечётно.

Автор задачи: Arpan Banerjee