408324: GYM103092 J Just One Left

J. Just One Leftограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Диас и Арыстан интересуются спортивным программированием и хотят попасть в ACM Club нашего чудесного SDU. Для этого они сходили на выставку клубов и выяснили, что туда попадают только те, кто готовят первоклассный маклюбе и способны решить одну непростую задачу. Диас и Арыстан не могли похвастаться кулинарными навыками и решили сначала научиться готовить, а вас попросили помочь с решением задачи, условие которой описано ниже.

Вам дан массив $$$a$$$ длины $$$n$$$ состоящий из положительных целых чисел. Обозначим $$$f(a)$$$ как массив $$$b$$$ длины $$$n-1$$$, где $$$b_i = gcd(a_1 + \dots + a_i, a_{i+1} + \dots + a_n)$$$. Будем применять операцию $$$a = f(a)$$$ до тех пор, пока размер массива $$$a$$$ не станет равным $$$1$$$. Выведите единственное оставшееся число в массиве.

Здесь $$$gcd(x, y)$$$ означает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Входные данные

В первой строке задано одно целое число $$$n$$$ – длина исходного массива ($$$2 \le n \le 10^{5}$$$).

Во второй строке набора записаны $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — элементы исходного массива $$$a$$$ ($$$1 \le a_i \le 10^9$$$).

Выходные данные

Выведите одно целое число — единственное оставшееся число в массиве.

ПримерВходные данные

3
4 6 8

Выходные данные

2

Примечание

Пояснение для первого примера:

• $$$a = [4, 6, 8]$$$
• $$$f(a) = [gcd(4, 14)$$$, $$$gcd(10, 8)]$$$ = $$$[2, 2]$$$
• $$$f(f(a)) = [gcd(2, 2)] = 2$$$