Софтвіль
У селі Софтвіль існує традиційний спосіб розробки програмного забезпечення: у перший день програміст пише кілька рядків коду (принаймні один рядок), а кожного наступного дня додає ще один рядок до попередньої кількості.
Коли житель Софтвіля досягає 10 років, він повинен пройти ініціацію, створивши з нуля складну програму. Ця програма має однаковий код для всіх і складається з рівно N рядків. Кожному жителю потрібна різна кількість днів, щоб завершити цю програму. Проте правило залишається незмінним: щодня програміст пише на один рядок більше, ніж попереднього дня.
Вам надано інформацію про те, скільки днів знадобилося кожному жителю для написання своєї програми. Ваше завдання — визначити найменше можливе значення N, тобто кількість рядків у програмі.
Вхідні дані
Перша строка вхідного файлу містить число m (1 ≤ m ≤ 1000) — кількість жителів Софтвіля. Друга строка містить m чисел, які вказують на кількість днів, протягом яких кожен житель працював над своєю програмою. Усі числа в другій строкі є додатними цілими числами, меншими за 2^63.
Вихідні дані
Вихід повинен містити єдине число — найменше можливе значення для N. Якщо вхідні дані не можуть бути узгоджені для жодного значення N, ви повинні вивести 0. Інакше гарантовано, що найменше можливе значення для N менше за 2^63.