P14453 [ICPC 2025 Xi'an R] Grand Voting

Dada 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 \geq a_i$, they cast an upvote, incrementing $s$ by $1$. - If $s < a_i$, they cast a downvote, decrementing $s$ by $1$. Dada can control the voting order of these $n$ people. He wants to know the maximum and minimum possible vote count $s$ in this contest.

The first line of input contains a single integer $n$ ($1 \leq n \leq 10^5$), representing the number of voters. The next line of input contains $n$ integers $a_1, a_2, \cdots, a_n$ ($|a_i| \leq 10^5$), separated by spaces.

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

For example, if you rearrange $a$ to $[-1, 0, 1, 2, 3]$, initially $s = 0$. Since $s \geq a_1 = -1$, the first voter casts an upvote, making $s = 1$. Similarly, the remaining four voters also satisfy $s \geq 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$.