У Юки есть последовательность $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$.