4355: T2 划分（partition）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
## T2 划分（partition）
### 题目描述
小 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)$ 的最大值。
样例输入 复制
5
1 2 3 1 2样例输出 复制
3提示
### 样例 1 输入
```
5
1 2 3 1 2
```
### 样例 1 输出
```
3
```
### 样例 2 输入
```
6
7 7 7 7 7 7
```
### 样例 2 输出
```
21
```
其余样例见下发文件。
### 数据规模与约定
- 对于 $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$。