Teams

Time limit2.5sMemory limit256 MB

Summary

Given each child's minimum required team size, partition all children into the maximum number of teams and then minimize the largest team size among optimal partitions.

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

Problem

A primary school is holding its sports day, and the highlight is the annual football cup. A group of children has gathered on the pitch to be split into teams, but they cannot agree on the rosters by themselves, so the coach decides to do it for them.

There are n children, numbered 1 through n. Child i announces that she will be unhappy unless her team has at least a_i players. In other words, the team that child i belongs to must contain at least a_i members.

The coach must place every child on exactly one team so that no child is unhappy. Among all such arrangements he first wants to maximize the number of teams. Then, among the arrangements that use that maximum number of teams, he wants the largest team to be as small as possible.

Input

The first line contains one integer n (1 ≤ n ≤ 1 000 000).

Each of the next n lines contains one integer a_i (1 ≤ a_i ≤ n): the minimum team size that keeps child i happy.

Output

Print two integers separated by a single space:

t — the maximum possible number of teams;
m — the smallest possible size of the largest team, taken over every way of forming exactly t teams while assigning all n children.

Both values are uniquely determined by the input.

Examples6

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