Андрей разложил у себя на столе \(n\) кучек с камнями. В кучке с номером \(i\) лежит \(a_i\) камней. Он хочет добиться того, что каждый камень будет лежать либо в кучке \(1\), либо в кучке \(n\).
Для этого Андрей может выполнить следующую операцию сколько угодно раз: выбрать \(3\) индекса \(1 \le i < j < k \le n\) такие, что в кучке \(j\) лежит хотя бы \(2\) камня, забрать \(2\) камня из кучки \(j\) и один из них положить в кучку \(i\), а второй в кучку \(k\).
Определите, за какое минимальное количество операций Андрей сможет переложить камни так, чтобы каждый камень лежал либо в кучке \(1\), либо в кучке \(n\), или скажите, что это сделать невозможно.
Выходные данные
Для каждого набора входных данных выведите минимальное число операций, которые надо сделать, чтобы каждый камень лежал либо в кучке \(1\), либо в кучке \(n\), или выведите \(-1\), если это сделать невозможно.
Примечание
В первом наборе входных данных оптимально сделать следующее:
- Выбрать \((i, j, k) = (1, 2, 5)\). Массив становится равным \([2, 0, 2, 3, 7]\).
- Выбрать \((i, j, k) = (1, 3, 4)\). Массив становится равным \([3, 0, 0, 4, 7]\).
- Затем два раза выбрать \((i, j, k) = (1, 4, 5)\). Массив становится равным \([5, 0, 0, 0, 9]\). Этот массив удовлетворяет условию задачи, потому что все камни лежат в \(1\)-й или \(5\)-й кучке.
Всего
\(4\) операции.
Во втором наборе входных данных положить все камни в кучки \(1\) и \(3\) невозможно:
- Изначально есть только один способ совершить операцию, выбрав \((i, j, k) = (1, 2, 3)\). Массив становится равным \([2, 1, 2]\).
- Теперь ни одной операции сделать невозможно, а массив не удовлетворяет условию задачи, поэтому ответ \(-1\).
В третьем наборе входных данных оптимально сделать следующее:
- Выбрать \((i, j, k) = (1, 2, 3)\). Массив становится равным \([2, 0, 2]\). Этот массив удовлетворяет условию задачи, потому что все камни лежат в \(1\)-й или \(3\)-й кучке.
Всего
\(1\) операция.
В четвёртом наборе входных данных изначально нельзя сделать ни одной операции, и исходный массив не удовлетворяет условию задачи, поэтому ответ \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|