Джон Сильвер с командой пиратов во время поиска места, где зарыты сокровища, наткнулись на очередную загадку Флинта. На карте написано, что им нужно пройти d шагов на север, чтобы прийти на место, где спрятан клад. Однако само число d пиратам неизвестно, сказано лишь то, что это было любимое число капитана Флинта.

Джон Сильвер долго плавал с капитаном Флинтом и очень хорошо его знал. Каждый раз, когда капитан пересчитывал свои богатства, он высыпал все золотые монеты на стол и складывал их в кучки по d, чтобы было удобнее считать. Все лишние монеты, которых не хватало для очередной кучки, он раздавал команде. Именно из-за частого подсчета денег число d и стало любимым для Флинта.

В день, когда Флинт с командой прибыли на остров, прежде чем спрятать сокровища, капитан, как обычно, решил их пересчитать. Затем взял n сундуков и начал складывать в них деньги. Он по очереди брал со стола кучку из d монет и клал ее всю в один из сундуков. Однако, когда на столе осталась всего одна кучка монет, внезапно несколько членов команды напали на Флинта с целью забрать все сокровища себе. Разумеется, они недооценили опыт капитана и сами пали в бою с ним. Флинт же осознал, что нужно торопиться, в спешке собрал оставшиеся монеты со стола и бросил их в 2 ближайших к нему сундука, не обращая внимания, сколько монет из кучки оказалось в каждом из них. Схватив свои сокровища, он отправился их закапывать.

Все это Джон Сильвер видел своими глазами, но пойти за Флинтом и узнать, где он хочет спрятать деньги, было опасно. Зато Сильвер смог запомнить, сколько монет было в каждом сундуке. Но он тогда не знал, что самой ценной информацией в тот момент было именно число d — размер кучек с монетами. И теперь Джон никак не может его вспомнить. Помогите ему определить наибольшее возможное число d, зная, сколько монет было в каждом сундуке.

В первой строке вводится целое число n – количество сундуков с деньгами (2 ≤ n ≤ 10⁵).

Во второй строке через пробел вводятся n целых чисел a_i – количество монет в каждом из сундуков (0 ≤ a_i ≤ 10¹²).

Гарантируется, что у Джона была хотя бы 1 монета.

Выведите единственное число – наибольшее возможное значение любимого числа Флинта – d.

В первом примере при d = 5 Флинт кинул бы 20 кучек монет в последний сундук, по 1 кучке в первый, второй и третий. А оставшуюся кучку кинул в сундуки 2 и 3. В третий сундук попало 2 монеты, во второй – 3.

Во втором примере в сундуки положили 3, 1, 2, 1 и 4 кучек монет соответственно. А последнюю кучку разделили между 2 и 4 сундуком по 1 и 2 монеты соответственно.