You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Statement

Timothy organized a contest, but it received heavy downvotes. He decided to start manipulating the comments.

This contest has $s$ votes, initially set to 0.

There are $n$ participants, each with a voting parameter $a_i$. When it’s their turn to vote:

• If $s \geqslant a_i$, they cast an upvote, incrementing $s$ by 1;
• If $s < a_i$, they cast $a$ downvote, decrementing $s$ by 1.

Timothy can control the voting order of these $n$ people. He wants to know the maximum and minimum possible vote count $s$ in this contest.

Input

The first line of input contains $a$ single integer $n (1 \leqslant n \leqslant 10^5)$, representing the number of voters.

The next line of input contains $n$ integers $a_1, a_2, \cdots , a_n (|a_i| \leqslant 10^5)$, separated by spaces.

Output

Output one line containing two integers separated by a space, representing the maximum and minimum vote count $s$ in this contest.

Samples

5
-1 0 1 2 3

5 -5

Note

For example, if you rearrange $a$ to $[−1, 0, 1, 2, 3]$, initially $s = 0$. Since $s \geqslant a_1 = −1$, the first voter casts an upvote, making $s = 1$. Similarly, the remaining four voters also satisfy $s \leqslant a_i$, so all cast upvotes. The final value of $s$ is 5, which is the maximum possible.

Conversely, if you rearrange $a$ to $[1, 2, 0, 3, −1]$, then for each voter from left to right, $s < a_i$ holds, so all cast downvotes, resulting in $s = −5$. This is the minimum possible. Another arrangement such as $[3, 2, 1, 0, −1]$ also leads to $s = −5$.