小 C 有一个长度为 n 的序列 A，现在他想把序列 A 划分成至少 2 段。

小 C 定义 l_i,r_i 表示划分出的第 i 个子段的左右端点，这个子段的子段和 b_i=\sum\limits_{j=l_i}^{r_i}A_j。

小 C 认为一个合法的划分需要满足 l_i\le r_i，且对于 \forall 1\le j\lt k，有 l_{j+1}=r_j+1，并且 l_1=1,r_k=n。(假设划分出了 k 段)

小 C 想要求一种划分方案使得 \gcd(b_1,b_2,...,b_k) 最大，你能告诉他该最大值吗？

输入的第一行包含一个整数 n。

接下来一行包含 n 个整数，第 i 个整数表示 A_i。

输出共一行，包含一个整数，表示 \gcd(b_1,b_2,...,b_k) 的最大值。

数据规模与约定

• 对于 30\% 的数据，保证 n \le 20。

• 对于另 30\% 的数据，保证 n \le 100，1\le A_i\le 3。

• 对于另 20\% 的数据，保证 A_i=1 且 2|n。

• 对于 100\% 的数据，保证 1 \le n \le 10^{5}，1\le A_i\le 10^9。