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

Недавно Монокарп создал свою собственную мини-лабораторию!

В его лаборатории содержится $$$n$$$ бактерий. Монокарп знает, что если соединить две бактерии одинакового размера, то из них получится одна бактерия вдвое большего размера. Например, если соединить две бактерии, каждая из которых имеет размер $$$7$$$, то получится одна бактерия с размером $$$14$$$.

Так как исследовать более одной бактерии неудобно, Монокарп хочет при помощи соединений бактерий сократить их количество в лаборатории до одной. Также Монокарп может купить в специализированном магазине любое количество бактерий любого размера.

Определите минимальное количество бактерий, которое Монокарпу нужно купить, чтобы при помощи соединений купленных бактерий, а также имеющихся $$$n$$$ бактерий, можно было оставить в лаборатории ровно одну бактерию.

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

В первой строке следует целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — количество бактерий.

Во второй строке следует последовательность из $$$n$$$ целых чисел $$$a_{1}, a_{2}, \dots, a_{n}$$$ $$$(1 \le a_{i} \le 10^9)$$$, где $$$a_i$$$ равно размеру $$$i$$$-й бактерии.

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

Если невозможно оставить в лаборатории ровно одну бактерию, выведите -1.

В противном случае, выведите минимальное количество бактерий, которое нужно купить в магазине, чтобы при помощи соединений купленных бактерий, а также имеющихся $$$n$$$ бактерий, можно было оставить в лаборатории ровно одну бактерию.

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

В первом примере нужно купить в магазине одну бактерию с размером $$$1$$$ и одну бактерию с размером $$$2$$$. Тогда у Монокарпа будет $$$4$$$ бактерии с размерами $$$[1, 4, 1, 2]$$$. После этого нужно соединить две бактерии с размерами $$$1$$$ и получить одну бактерию с размером $$$2$$$. После этого у Монокарпа будет $$$3$$$ бактерии с размерами $$$[2, 4, 2]$$$. После этого нужно соединить две бактерии с размерами $$$2$$$ и получить одну бактерию с размером $$$4$$$. После этого у Монокарпа станет $$$2$$$ бактерии с размерами $$$[4, 4]$$$, которые можно соединить в одну бактерию с размером $$$8$$$.

Во втором примере невозможно купить бактерии таким образом, чтобы после соединений количество бактерий стало равно одному.

В третьем примере нужно купить одну бактерию с размером $$$1000000000$$$.