N (\(1≤N≤10^5\)) корів Фермера Джона вишикувані в ряд так, що i-а корова в цьому ряду має рівень голоду hi (\(0≤h_i≤10^9\)). Оскільки корови - соціальні тварини і хочуть їсти разом, єдиний спосіб зменшити рівень голоду його корів - вибрати двох сусідніх корів із номерами i та i+1 та згодувати кожній з них по мішку кукурудзи, щоб зменшити рівень голоду кожної з них на один.

ФД хоче нагодувати своїх корів так, щоб усі мали один і той же деякий не відʼємний рівень голоду. Допоможіть ФД визначити мінімальну кількість мішків кукурудзи, яка йому буде потрібна, або -1, якщо це зробити неможливо.

Формат вхідних даних

Кожне введення складається з кількох незалежних тестів, кожен з яких потрібно вирішити правильно, щоб повністю вирішити вхідний тест. Перший рядок містить T (1≤T≤100) – кількість тестів у введенні. Кожен тест описується кількома рядками. Перший рядок у парі містить N, а другий - \(h_1,h_2,...,h_N\). Гарантується, що сума всіх N у тесті не перевищить \(10^5\). Значення N можуть бути різними всередині введення.

Формат вихідних даних

Виведіть T рядків по одному для кожного тесту на введенні. Зауважимо, що потрібно використовувати 64-бітове ціле для відповіді (наприклад "long long" в C/C++)

Приклад вхідних даних

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

Для першого тесту даємо по два мішки кукурудзи корів 2 і 3, потім по п'ять мішків коровам 1 і 2, в результаті рівень голоду всіх корів стане 3.

У другому випадку даємо по два мішки корів 1 м 2, потім по два мішки коровам 2 і 3, потім по два мішки коровам 4 і 5, і по два мішки коровам 5 і 6 - як результат у всіх корів рівень голоду 2.

У решті випадків неможливо зробити однаковими рівні голоду всіх корів.

ОЦІНЮВАННЯ:

• У тесті 2 N≤3 та \(h_i≤100\).
• У тестах 3-8 N≤100 та \(h_i≤100\).
• У тестах 9-14 N≤100.
• У тесті 15 немає додаткових обмежень.

Крім того, N завжди парне у тестах 3-5 та 9-11, і N завжди непарне у тестах 6-8 та 12-14.

Автор: Arpan Banerjee