У Юкі є послідовність $a$ довжини $n$.

Юкі визначає операцію таким чином:

• Виберіть відрізок $[l, r]$ парної довжини. Для кожного цілого $i$ такого, що $l \le i \le r$:
  • Якщо $i - l$ непарне, значення $a_i$ зменшується на $1$, тобто $a_i \leftarrow a_i - 1$.
  • Якщо $i - l$ парне, значення $a_i$ збільшується на $1$, тобто $a_i \leftarrow a_i + 1$.

Тепер Юкі хоче виконати деяку кількість операцій так, щоб усі числа в послідовності $a$ стали рівними. Вам потрібно допомогти Юкі знайти мінімальну кількість операцій, необхідну для того, щоб зробити всі числа в послідовності $a$ рівними, або повідомити, що це неможливо.

Вхідні дані

Ця задача містить декілька наборів вхідних даних.

Перший рядок містить додатне ціле число $t$ ($1 \le t \le 10^5$), що позначає кількість наборів вхідних даних.

Для кожного набору вхідних даних:

• Перший рядок містить додатне ціле число $n$ ($1 \le n \le 10^6$).
• Другий рядок містить $n$ цілих чисел $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

Гарантується, що сума $n$ за всіма наборами вхідних даних не перевищує $10^6$.

Вихідні дані

Для кожного набору вхідних даних виведіть один рядок:

• Якщо це неможливо, виведіть $-1$.
• Якщо це можливо, виведіть ціле число — мінімальну кількість операцій, щоб зробити всі числа в послідовності $a$ рівними.

Приклади

Вхідні дані 1

3
2
1 3
4
1 5 1 5
5
1 3 1 3 1

Вихідні дані 1

1
2
-1

Примітка

Для першого набору вхідних даних:

• Виконаємо операцію на відрізку $[1, 2]$. Послідовність перетвориться на $2, 2$, де всі числа рівні.
• Можна довести, що розв'язку з меншою кількістю операцій не існує, тому відповідь дорівнює $1$.

Для другого набору вхідних даних:

• Виконаємо операцію на відрізку $[1, 4]$. Послідовність перетвориться на $2, 4, 2, 4$.
• Виконаємо операцію на відрізку $[1, 4]$. Послідовність перетвориться на $3, 3, 3, 3$, де всі числа рівні.
• Можна довести, що розв'язку з меншою кількістю операцій не існує, тому відповідь дорівнює $2$.

Для третього набору вхідних даних:

• Легко довести, що зробити всі числа рівними неможливо незалежно від кількості операцій, тому відповідь дорівнює $-1$.