Packing Balls 2

Time limit2sMemory limit512 MB

Summary

Given counts of balls in K colors, pack them into boxes of capacity K where each box is all one color or all distinct colors, using as few boxes as possible.

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

Problem

The balls come in $K$ colors. A color is an integer from 1 to $K$ , and there are $X_i$ balls of color $i$ .

You want to pack all of the balls into boxes. One box holds at most $K$ balls.

The balls inside one box must all have different colors, or must all have the same color.

Write a program that finds the minimum number of boxes you need.

Input

The first line contains the number of colors $K$ . ( $1 \le K \le 100{,}000$ )

The second line contains $X_1, X_2, \dots, X_K$ , the ball counts of color 1 through color $K$ , separated by spaces. ( $1 \le X_i \le 1{,}000{,}000{,}000$ )

Output

Print the minimum number of boxes on the first line.

Examples4

Example 1
Input
```
3
4 2 4
```
Expected output
```
4
```
Example 2
Input
```
1
58
```
Expected output
```
58
```
Example 3
Input
```
7
1 6 6 6 6 6 6
```
Expected output
```
6
```
Example 4
Input
```
5
5 3 5 3 5
```
Expected output
```
5
```