Plant Watering

Time limit1sMemory limit1024 MB

Summary

Given N plants that wilt after a_i days without water (each a_i a power of 2), find the minimum number X of plants to water each day so that none wilts forever.

Level: Medium7 of 10
Topics: Greedy, Math, Bit manipulation
Solved: No attempts yet

Problem

Uijin planted $N$ plants in a field this morning. The $i$ -th plant wilts if it goes $a\_i$ consecutive days without water. Oddly, every $a\_i$ is a power of $2$ .

Uijin watered all the plants this morning. Starting tomorrow, Uijin told Minseok to water only $X$ of the $N$ plants each morning. Minseok does his best to keep every plant from wilting forever, choosing $X$ plants to water each day.

Depending on $X$ , it may be impossible to keep every plant alive forever. Uijin wants to pick a suitable $X$ and tell Minseok. Find the minimum $X$ for which Minseok can keep all plants from wilting forever.

Input

The first line contains an integer $N$ ( $1\le N\le 100\,000$ ).

The second line contains integers $a\_1,a\_2,\cdots ,a\_N$ ( $1\le a\_i\le 2^{16};$ $a\_i$ is a power of $2$ ), separated by spaces.

Output

Print the minimum $X$ for which Minseok can keep all plants from wilting forever when he does his best.

Hint

The image in the statement is a Touhou Project fan work drawn by the problem setter.

Examples3

Example 1
Input
```
4
4 2 2 1
```
Expected output
```
3
```
Example 2
Input
```
2
1 1
```
Expected output
```
2
```
Example 3
Input
```
5
4 16 2 32 8
```
Expected output
```
1
```