← 返回题目列表

Codeforces · 388/A

A. 狐狸和盒子积累

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

Fox Ciel 的房间里有 n 个盒子。它们具有相同的尺寸和重量,但强度可能不同。第 i 个盒子的顶部最多可以容纳 xi 个盒子(我们将 xi 称为盒子的强度)。

由于所有盒子的大小相同,Ciel 无法将多个盒子直接放在某个盒子的顶部。例如,假设 Ciel 有三个盒子:第一个盒子的强度为 2,第二个盒子的强度为 1,第三个盒子的强度为 1。她不能同时将第二个和第三个盒子直接放在第一个盒子的顶部。但她可以将第二个盒子直接放在第一个盒子的顶部,然后将第三个盒子直接放在第二个盒子的顶部。我们将这种盒子结构称为堆。

Fox Ciel 想要用所有盒子堆砌一堆。每堆从上到下都会包含一些盒子,并且第 i 个盒子的顶部不能超过 xi 个盒子。她需要建造的最少桩数是多少?

输入

第一行包含一个整数 n (1 ≤ n ≤ 100)。下一行包含 n 个整数 x1, x2, ..., xn (0 ≤ xi ≤ 100)。

输出

输出一个整数——最小可能的堆数。

示例

输入 #1

3
0 0 10

输出 #1

2

输入 #2

5
0 1 2 3 4

输出 #2

1

输入 #3

4
0 0 0 0

输出 #3

4

输入#4

9
0 1 0 2 0 1 1 2 10

输出#4

3

注意

在示例 1 中,一种最佳方法是构建 2 堆:第一堆包含盒子 1 和 3(从上到下),第二堆仅包含盒子 2。

在示例 2 中,我们只能构建 1 堆包含盒子 1、2、3、4、5(从上到下)的堆。