Рух у лабіринті#4413
Ваш начальник доручив вам створити лабіринт для прогулянок, і ви розглядаєте різні варіанти дизайну. Перш ніж вибрати остаточний, ви хочете дізнатися, наскільки швидко люди можуть пересуватися в кожному з лабіринтів. Адже ваш начальник зацікавлений у прибутковості цього підприємства, і чим швидше люди можуть пройти, тим більше платних клієнтів ви зможете обслуговувати.
Лабіринт складається з пронумерованих кімнат і проходів, що з'єднують ці кімнати. Єдиний вхід до лабіринту знаходиться в кімнаті з найменшим номером, а єдиний вихід — у кімнаті з найбільшим номером.
Кожен прохід має обмеження на кількість людей, які можуть пройти одночасно. Для двох кімнат з номерами і , якщо і мають спільний дільник більший за одиницю, то між і існує прохід. Найбільший спільний дільник визначає кількість людей за хвилину, які можуть пройти з до . Одночасно, людей за хвилину можуть також рухатися з до . Вхід, вихід і кімнати можуть пропускати будь-яку кількість людей одночасно. Люди прагнуть пройти лабіринт якомога швидше, тому вони не затримуються в кімнатах.
Ось ілюстрації двох прикладів вхідних даних. Коробки представляють пронумеровані кімнати, і кожна стрілка — це прохід, позначений кількістю людей за хвилину, які можуть пройти через нього.
Вхідні дані описують один лабіринт. Перша строка містить ціле число 2 \le n \le 1000, що вказує на кількість кімнат у лабіринті. Далі йдуть унікальних цілих чисел, по одному на рядок, які є номерами кімнат у лабіринті. Кожен номер кімнати знаходиться в діапазоні [2, 2 \times 10^9].
Виведіть максимальну кількість людей за хвилину, які можуть увійти в лабіринт, припускаючи, що люди виходять з лабіринту з такою ж швидкістю, як і входять. Жоден лабіринт не підтримує більше ніж 10^9 людей, що входять за хвилину.
Приклад 1