eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Подготовка к битве

Подготовка к битве

Лимит времени 0.4 секунд
Лимит использования памяти 64 MiB

Выдающийся маршал Ла Шрам считает лучшей боевой единицей отряд, построеный в две шеренги одинаковой численности во главе с командиром. Поэтому он должен состоять из нечетного количества воинов. Но на его призыв иногда являются отряды и с четным количеством бойцов. Тогда он самостоятельно вызывает на плац все отряды с некоторым четным количеством бойцов q для проведения операций деления. После выполнения его команд эти отряды делятся на равные части, одна из которых остается в его армии, а другая переводится в резерв. Такие операции повторяются, пока все отряды не будут иметь нечетное количество солдат. Определите, какое наименьшее количество операций маршалу придется сделать, чтобы остались отряды с желаемым составом. Например, если первоначальный состав отрядов имеет вид: [22, 31, 52, 13, 26, 11, 26], то можно: построить отряды с количеством воинов q = 22, разделить их, получим: [11, 31, 52, 13, 26, 11, 26]; потом с q = 52, имеем: [11, 31, 26, 13, 26, 11, 26]; и, наконец, с q = 26: [11, 31, 13, 13, 13, 11, 13]. Таким образом за три шага реорганизация будет завершена.

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

Программа вводит с клавиатуры одно натуральное число: N (от 5 до 10 ^ 6) - число отрядов, а затем в следующей строке N натуральных чисел от (11 до 10 ^ 9) - численности отрядов.####Выходные данныеВ единственной строке записать минимальное количество операций деления для проведения реорганизации.

Пример

Входные данные #1
7
22 31 52 13 26 11 26
Выходные данные #1
3
Источник Открытая ученическая олимпиада Днепра по информатике 2020