27944번 - 가지 이모지

문제

가지컵 출제를 위한 디스코드 채팅방에서는 메시지에 가지 이모지로 반응을 달 수 있다. kiwiyou가 보낸 메시지에 가지 이모지가 $N$종류 달려 있고, $i$번째 가지 이모지에 반응이 $A_i$개 달려 있다고 하자. (1ドル\le i\le N$)

민규는 각 이모지에 반응을 최대 한 번만 할 수 있다. 민규가 $i$번째 이모지에 반응을 한다면 $i$번째 이모지의 반응 개수가 $A_i$에서 $A_i + 1$로 변한다.

메시지 아래에 각 이모지와 반응 개수가 적혀 있다. $A=[2,6,8,9,5]$에서 반응 후 $B=[3,6,9,9,6]$이 되었다.

민규가 0ドル$개 이상의 이모지에 반응을 한 후 $i$번째 이모지의 반응 개수를 $B_i$라고 하자. 메시지의 반응 개수에 대한 민규의 만족도는 $\gcd(B_1,$ $B_2,$ $\cdots,$ $B_n)$으로 정의된다.

민규가 적절히 반응을 해서 얻을 수 있는 최대의 만족도를 구하자.

입력

첫째 줄에 이모지의 종류 수 $N$이 주어진다. $(1\le N\le 5 \times 10^5)$

둘째 줄에 각 이모지의 개수 $A_i$가 주어진다. $(1\le A_{i}\le 10^{12})$

출력

첫째 줄에 민규가 적절히 반응을 해서 얻을 수 있는 최대 만족감을 출력한다.

제한

힌트