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 р.