Problem F
Snoozed Alarm
Gene Block loves sleeping. Every morning, he is awakened by an alarm at a set time, and hits the snooze button repeatedly until he is ready to wake up. In fact, to analyze his sleeping habits, Gene has compiled all the times at which his alarm went off in the past several days, including the initial alarm and the possible subsequent alarms resulting from hitting the snooze button. However, all Gene has is this list of times (which may be in any order), and does not remember how many days this data corresponds to or what the fixed snooze period $k \geq 1$ is. Please help Gene Block figure out what the minimum and maximum possible number of days this data could represent.
In particular, each day, the initial alarm can be set to a different time, but the snooze period is fixed at a time period of $k$. For example, if there was one day of alarm data, one where the initial alarm was $t = 1$, and Gene hit the snooze $4$ times, where the snooze time was $k = 2$, then the times where the alarm went off would be $t = 1, 3, 5, 7, 9$.
Your goal is to take a set of times such as $1, 3, 5, 7, 9$ and output the minimum and maximum number of days these times could be partitioned into. In this case, the minimum number of days is $1$, where the snooze period $k$ is $2$, and the maximum number of days is $5$, where each day, Gene does not hit the snooze button at all, and the alarm is set initially to the times $t = 1, 3, 5, 7, 9$. In this case, the snooze period $k$ is irrelevant and could be any number.
Input
The first line contains $n \leq 10^5$, the number of times that Gene Block has recorded. The second line contains $n$ space-separated integers $t_ i$, $0 \leq t_ i < 1\, 440$ (1440 is the number of minutes in a day), the times that Gene has recorded, given in any order and possibly containing duplicate times.
Output
The output should contain two integers, the minimum and maximum number of days the data could represent.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 2 3 4 5 |
1 5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1439 0 1 |
2 3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 1 3 5 7 9 |
1 5 |
| Sample Input 4 | Sample Output 4 |
|---|---|
8 1 4 7 10 13 9 5 1 |
4 8 |
