← 返回题目列表

Codeforces · 792/E

E. 彩色球

中文机器翻译题面 查看原题

桌子上有 n 个装有彩球的盒子。颜色从 1 到 n 编号。第 i 个盒子包含 ai 球,所有球的颜色均为 i。您必须编写一个程序,将所有球分成几组,以便:

- 每个球都属于一组,
- 没有空集,
- 没有包含两个(或更多)不同颜色的球的集合(每组仅包含一种颜色的球),
- 没有两个集合的大小之差大于 1。

打印尽可能少的份数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 500)。

第二行包含 n 个整数 a1, a2, ... , an (1 ≤ ai ≤ 109)。

输出

打印一个整数——可能的最小组数。

示例

输入 #1

3
4 7 8

输出 #1

5

输入 #2

2
2 7

输出 #2

4

注意

在第一个示例中,球可以分为这样的组:一组有 4 个第一种颜色的球,两组分别有 3 个和 4 个第二颜色的球,两组有 4 个第三种颜色的球。