Є \(N\) монстрів, які пронумеровані від 1 до \(N\).

На початку здоров'я монтра \(i\) дорівнює \(A_i\) і принаймні 1 монстр живий.

Поки не залишиться лише один живий монстр виконуємо наступне:

• випадковий монстр атакує іншого випадкового живого монстра;

• в результаті атаки здоров'я атакованого монстра зменшується на величину, що дорівнює поточному здоров'ю атакуючого монстра.

Знайдіть мінімально можливе залишкове здоров'я останнього живого монстра.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) (\(2 \le N \le 10^5\)).

Наступний рядок містить здоров'я монстрів \(A_i\) (\(1 \le i \le N\), \(1 \le A_i \le 10^9\)).

Числа у рядку розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести мінімально можливе залишкове здоров'я останнього живого монстра.

Приклад вхідних даних

4
2 10 8 40

Приклад вихідних даних

2

Приклад вхідних даних

4
5 13 8 1000000000

Приклад вихідних даних

1

Приклад вхідних даних

3
1000000000 1000000000 1000000000

Приклад вихідних даних

1000000000