题目描述

现在有 $n$ 种不同颜色的求，其中第 $i$ 种颜色的球有 $a_i$ 个。现在你需要把这些球分成若干堆，且满足如下规则：

• 每一堆的球都必须具有相同的颜色（即不存在两个不同颜色的球在同一堆）；
• 任意两堆的球的数量相差不超过 $1$。

求满足条件的最少堆数。

输入格式

输入的第一行包含一个整数 $n(1 \le n \le 500)$，表示颜色数。

输入的第二行包含 $n$ 个整数，两两之间以一个空格分隔，其中第 $i$ 个整数表示第 $i$ 种颜色的球的个数 $a_i(1 \le a_i \le 10^9)$。

输出格式

输出一个整数，表示满足上述两个规则限制的情况下最少能够分成的堆数。

样例

3
4 7 8

5

2
2 7

4

样例解释

• 样例1中，第 $1$ 种颜色可以分成 $1$ 堆（包含 $4$ 个球）；第 $2$ 种颜色可以分成 $2$ 堆（一对包含 $4$ 个球，另一堆包含 $3$ 个球）；第 $3$ 种颜色可以分成 $2$ 堆（均包含 $4$ 个球）。
• 样例2中，第 $1$ 种颜色可以分成 $1$ 堆，第 $2$ 种颜色可以分成 $3$ 堆（其中两堆各包含 $2$ 个球，一堆包含 $3$ 个球）。

数据范围

• 对于 $20\%$ 的数据，$n \le 10, a_i \le 100$；
• 对于 $60\%$ 的数据，$n \le 50, a_i \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le n \le 500, 1 \le a_i \le 10^9$。