John Silver and his crew of pirates, while searching for the place where the treasures are buried, stumbled upon yet another riddle from Flint. The map states that they need to take d steps north to reach the spot where the treasure is hidden. However, the number d is unknown to the pirates; it is only mentioned that it was Captain Flint’s favorite number.

John Silver sailed with Captain Flint for a long time and knew him very well. Every time the captain counted his riches, he would pour all the gold coins onto the table and stack them in piles of d to make counting easier. Any leftover coins that did not fit into the next pile were given to the crew. It was precisely because of the frequent counting of money that the number d became Flint’s favorite.

On the day when Flint and the crew arrived on the island, before hiding the treasures, the captain, as usual, decided to count them. He then took n chests and began to fill them with money. He took a pile of d coins from the table one by one and placed it entirely into one of the chests. However, when there was only one pile of coins left on the table, several crew members suddenly attacked Flint in an attempt to take all the treasures for themselves. Naturally, they underestimated the captain’s experience and fell in battle against him. Flint realized that he needed to hurry; in a rush, he gathered the remaining coins from the table and threw them into the two nearest chests, not paying attention to how many coins from the pile ended up in each of them. Grabbing his treasures, he set off to bury them.

John Silver saw all this with his own eyes, but it was dangerous to follow Flint and find out where he wanted to hide the money. However, Silver was able to remember how many coins were in each chest. But he did not know that the most valuable information at that moment was the number d — the size of the piles of coins. And now John cannot recall it. Help him determine the largest possible number d, knowing how many coins were in each chest.

The first line contains an integer n — the number of chests with money (2 ≤ n ≤ 10⁵).

In the second line, n integers a_i are given through spaces — the number of coins in each of the chests (0 ≤ a_i ≤ 10¹²).

It is guaranteed that John had at least 1 coin.

Output a single number — the largest possible value of Flint’s favorite number — d.

In the first example, with d = 5, Flint would have thrown 20 piles of coins into the last chest, one pile into the first, second, and third chests. The remaining pile was split between chests 2 and 3. The third chest received 2 coins, while the second received 3.

In the second example, 3, 1, 2, 1, and 4 piles of coins were placed in the chests, respectively. The last pile was divided between chests 2 and 4 with 1 and 2 coins, respectively.