Підготовка до битви#9083
Видатний маршал Ла Шрам вважає найкращою бойовою одиницею загін, вишикуваний у дві шеренги однакової чисельності на чолі з командиром. Тому він повинен складатися з непарної кількості воїнів.
Але на його заклик іноді з’являються загони і з парною кількістю бійців. Тоді він самотужки викликає на плац всі загони з деякою парною кількістю бійців для проведення операцій поділу. Після виконання його команд ці загони діляться на рівні частини, одна з яких залишається у його армії, а інша переводиться у резерв. Такі операції повторюються, поки всі загони не будуть мати непарну кількість солдатів.
Визначте, яку найменшу кількість операцій маршалу доведеться зробити, щоб лишилися загони з бажаним складом.
Наприклад, якщо початковий склад загонів має вигляд: [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].Таким чином, за три кроки реорганізація буде завершена.
Програма вводить з клавіатури одне натуральне число: (5 \le N \le 10^6) — число загонів, а потім у наступному рядку натуральних чисел a_1, a_2, \ldots, a_N (11 \le a_i \le 10^9) — чисельності загонів.
В єдиному рядку запишіть мінімальну кількість операцій поділу для проведення реорганізації.
Приклад 1