回家的路

题目描述

有 n 只青蛙，编号为 1 到 n（第 i 只青蛙的编号为 i），它们最初都位于坐标 0。每秒钟，第 i 只青蛙向前跳跃的长度为 $d_i$。这些青蛙准备沿着一条直线回家，所有青蛙的跳跃方向相同。

在任何青蛙跳跃之前，小珅想在某一个整数坐标上放置一个捕捉器，用来捕捉经过这个点的青蛙，即跳跃后停留在该位置上的青蛙。小珅只能在坐标 1 到 n 之间的点放置一个捕捉器。请你帮助小珅计算最多可以捕捉多少只青蛙。

输入描述

第一行包含一个整数 n。

第二行包含 n 个整数 $d_1$、$d_2$、……、$d_n$。

输出描述

一行一个整数，表示答案。

样例 1

输入：

5
1 2 3 4 5

输出：

3

样例 1 解释：青蛙 1 按 0→1→2→3→4→5→…… 跳跃；青蛙 2 按 0→2→4→6→8→…… 跳跃；青蛙 3 按 0→3→6→9→12→…… 跳跃；青蛙 4 按 0→4→8→12→16→…… 跳跃；青蛙 5 按 0→5→10→15→20→…… 跳跃。因此，如果小珅在坐标 4 处放置捕捉器，可以捕获三只青蛙：青蛙 1、2 和 4。

样例 2

输入：

4
2 2 2 2

输出：

4

样例 2 解释：小珅可以在坐标 2 处放置捕捉器，捕获所有四只青蛙。

样例 3

输入：

9
1 3 2 4 2 3 7 8 5

输出：

5

数据范围

对于 50% 的数据保证：1 ≤ n ≤ 2×10^3。