Вам дан массив положительных целых чисел \(a_1, a_2, \ldots, a_n\).
Сделайте так, чтобы произведение всех чисел массива, то есть \(a_1 \cdot a_2 \cdot \ldots \cdot a_n\), делилось на \(2^n\).
Вы можете выполнять следующую операцию сколько угодно раз:
- выберите произвольный индекс \(i\) (\(1 \leq i \leq n\)) и замените значение \(a_i\) на \(a_i=a_i \cdot i\).
Вы не можете применять операцию повторно к одному индексу. Иными словами, все выбранные значения \(i\) должны быть различны.
Найдите, какое наименьшее количество операций нужно выполнить, чтобы произведение всех чисел массива делилось на \(2^n\). Обратите внимание, что не всегда такой набор операций существует.
Выходные данные
Для каждого набора входных данных выведите наименьшее количество операций, которое нужно сделать, чтобы произведение всех чисел массива делилось на \(2^n\). Если ответа не существует, то выведите -1.
Примечание
В первом наборе входных данных произведение чисел изначально равно \(2\), поэтому можно не применять операции.
Во втором наборе входных данных произведение чисел изначально равно \(6\). Мы можем применить операцию для \(i = 2\), и тогда \(a_2\) станет равно \(2\cdot2=4\), а произведение чисел станет равно \(3\cdot4=12\), а это произведение чисел делится на \(2^n=2^2=4\).
В четвертом наборе входных данных даже если мы применим все возможные операции, то у нас все равно не получится сделать произведение чисел кратным \(2^n\) — оно будет равно \((13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304\), что не делится на \(2^n=2^4=16\).
В пятом наборе входных данных можно применить операции для \(i = 2\) и \(i = 4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
2
2
3 2
3
10 6 11
4
13 17 1 1
5
1 1 12 1 1
6
20 7 14 18 3 5
|
0
1
1
-1
2
1
|