| Codeforces Round 228 (Div. 1) |
|---|
| Закончено |
У лисы Сиель в комнате есть n коробок. Все коробки имеют одинаковый размер и вес, но могут иметь различную прочность. Формально, i-ая коробка может выдержать не больше xi коробок на себе (будем называть xi прочностью коробки).
Так как у всех коробок одинаковый размер, Сиель не может поставить больше одной коробки непосредственно на некоторую коробку. Предположим, что у Сиель есть три коробки: у первой прочность 2, у второй прочность — 1, и у третьей — прочность 1. Нельзя одновременно поставить вторую и третью коробку прямо на первую. Но можно поставить вторую коробку прямо на первую, а затем третью коробку прямо на вторую. Назовем такое сооружение из коробок стопкой.
Лиса Сиель хочет соорудить стопки изо всех коробок. В каждой стопке может быть несколько коробок, но нельзя ставить больше xi коробок на i-ую коробку. Какое минимальное количество стопок может построить Сиель, используя все коробки?
В первой строке записано целое число n (1 ≤ n ≤ 100). В следующей строке записано n целых чисел x1, x2, ..., xn (0 ≤ xi ≤ 100).
Выведите целое число — минимальное возможное количество стопок.
3
0 0 10
2
5
0 1 2 3 4
1
4
0 0 0 0
4
9
0 1 0 2 0 1 1 2 10
3
В первом примере оптимальный способ — соорудить 2 стопки: в первой стопке будут коробки номер 1 и 3 (сверху вниз), во второй стопке будет только коробка номер 2.
Во втором примере можно построить одну стопку, содержащую коробки номер 1, 2, 3, 4, 5 (сверху вниз).
