桌子上有 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 个第三种颜色的球。