Firewood Pile

Time limit1sMemory limit1024 MB

Summary

Given N logs of given lengths, stack them in alternating single-log and crosswise layers, each layer sized by the logs below, to minimize total pile height.

Level: Medium7 of 10
Topics: Greedy, Sorting, Binary search, Implementation
Solved: No attempts yet

Problem

Adomas is getting ready for winter and has bought $N$ logs of firewood. All the logs have the same diameter, but they may have different lengths. Adomas wants to stack all of them in his cellar.

He builds the pile like this:

He lays the first log flat on the floor.
On top of it he lays as many logs as possible, each placed crosswise (perpendicular) to the log below. A log of length $L$ can support at most $L$ logs laid across it.
On top of that layer he lays a single log again, crosswise to the logs beneath it. This single log may be no longer than the number of logs directly below it.
On top of that single log he again lays as many crosswise logs as possible, and so on — alternating between one single log and one full crosswise layer.

An example of a firewood pile

Figure 1. An example of a firewood pile.

All logs share the same diameter, so every layer has the same thickness. The height of the pile is therefore the number of layers it consists of: each single log counts as one layer, and each crosswise group of logs counts as one layer.

Adomas is not very tall, so he wants the pile to be as low as possible. Given the lengths of all the logs, find the smallest possible height of the pile built in the described way.

Input

The first line contains the number of logs $N$ .

The second line contains $N$ space-separated integers $L_i$ — the lengths of the logs.

Output

Print a single integer — the smallest possible height of the firewood pile.

Constraints

$1 \le N \le 10^6$
$1 \le L_i \le 10^6$ (for $1 \le i \le N$ )

Examples2

Example 1
Input
```
5
1 1 2 1 1
```
Expected output
```
4
```
Example 2
Input
```
8
2 2 5 3 1 2 7 3
```
Expected output
```
2
```