C. Андрей и камни
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андрей разложил у себя на столе $$$n$$$ кучек с камнями. В кучке с номером $$$i$$$ лежит $$$a_i$$$ камней. Он хочет добиться того, что каждый камень будет лежать либо в кучке $$$1$$$, либо в кучке $$$n$$$.

Для этого Андрей может выполнить следующую операцию сколько угодно раз: выбрать $$$3$$$ индекса $$$1 \le i < j < k \le n$$$ такие, что в кучке $$$j$$$ лежит хотя бы $$$2$$$ камня, забрать $$$2$$$ камня из кучки $$$j$$$ и один из них положить в кучку $$$i$$$, а второй в кучку $$$k$$$.

Определите, за какое минимальное количество операций Андрей сможет переложить камни так, чтобы каждый камень лежал либо в кучке $$$1$$$, либо в кучке $$$n$$$, или скажите, что это сделать невозможно.

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

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — длина массива.

Во второй строке набора задана последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите минимальное число операций, которые надо сделать, чтобы каждый камень лежал либо в кучке $$$1$$$, либо в кучке $$$n$$$, или выведите $$$-1$$$, если это сделать невозможно.

Пример
Входные данные
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2
Выходные данные
4
-1
1
-1
Примечание

В первом наборе входных данных оптимально сделать следующее:

  1. Выбрать $$$(i, j, k) = (1, 2, 5)$$$. Массив становится равным $$$[2, 0, 2, 3, 7]$$$.
  2. Выбрать $$$(i, j, k) = (1, 3, 4)$$$. Массив становится равным $$$[3, 0, 0, 4, 7]$$$.
  3. Затем два раза выбрать $$$(i, j, k) = (1, 4, 5)$$$. Массив становится равным $$$[5, 0, 0, 0, 9]$$$. Этот массив удовлетворяет условию задачи, потому что все камни лежат в $$$1$$$-й или $$$5$$$-й кучке.
Всего $$$4$$$ операции.

Во втором наборе входных данных положить все камни в кучки $$$1$$$ и $$$3$$$ невозможно:

  1. Изначально есть только один способ совершить операцию, выбрав $$$(i, j, k) = (1, 2, 3)$$$. Массив становится равным $$$[2, 1, 2]$$$.
  2. Теперь ни одной операции сделать невозможно, а массив не удовлетворяет условию задачи, поэтому ответ $$$-1$$$.

В третьем наборе входных данных оптимально сделать следующее:

  1. Выбрать $$$(i, j, k) = (1, 2, 3)$$$. Массив становится равным $$$[2, 0, 2]$$$. Этот массив удовлетворяет условию задачи, потому что все камни лежат в $$$1$$$-й или $$$3$$$-й кучке.
Всего $$$1$$$ операция.

В четвёртом наборе входных данных изначально нельзя сделать ни одной операции, и исходный массив не удовлетворяет условию задачи, поэтому ответ $$$-1$$$.