该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

切巧克力

题目背景

小 R 的生日礼物是一整条手工巧克力，上面连着一排方糖。他打算把这条巧克力切开分给在场的每个人，而且坚持要「人人平等」：每一段的甜度必须完全相同，一段也不能多、一段也不能少。

题目描述

这条巧克力由 $n$ 块方糖连成一条，从左到右第 $i$ 块的甜度是 $a_i$。小 R 只能沿着两块方糖之间的缝隙下刀：一次切分把整条巧克力分成若干个连续非空的段，这些段首尾相接，恰好覆盖整条巧克力。

一段的甜度定义为这段内所有方糖甜度之和。小 R 要求切出的每一段甜度都相等。在此前提下，他希望段数尽量多。

请你求出最多能切成的段数。注意：不切也算切成了 $1$ 段，所以答案总是存在，且至少为 $1$。

输入格式

从标准输入读入数据。

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示从左到右每块方糖的甜度。

输出格式

输出到标准输出。

输出一行一个整数，表示最多能切成的段数。

样例 1 输入

4
1 1 1 1

样例 1 输出

4

样例 1 解释

把四块方糖各切为一段，每段甜度都是 $1$，段数最多为 $4$。

样例 2 输入

5
2 2 4 1 3

样例 2 输出

3

样例 2 解释

总甜度为 $12$。若切成 $4$ 段，每段甜度应为 $3$，但从左往右累计永远凑不出 $3$ 的整数倍切点，做不到。切成 $3$ 段时每段甜度为 $4$，切法为 $[2,2]\;[4]\;[1,3]$，故答案为 $3$。

数据范围

特殊性质 A：所有 $a_i$ 都相等。

特殊性质 B：设 $P_i = a_1 + a_2 + \dots + a_i$，对于所有 $1 \le i < n$，$P_i$ 都不是 $P_n$ 的约数。

对于所有测试数据，$1 \le n \le 5000$，$1 \le a_i \le 10^9$。

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。