Taming the Herd#10407
Early in the morning, Farmer John woke up to the sound of splintering wood. It was the cows, and they were breaking out of the barn again!
Farmer John was sick and tired of the cows' morning breakouts, and he decided that enough was enough: it was time to get tough. He nailed a counter to the barn wall that tracks the number of days since the last breakout. So if a breakout occurred in the morning, the counter would read that day; if the most recent breakout was days ago, the counter would read . Every day, Farmer John meticulously recorded the counter value in his log.
The end of the year has come, and Farmer John is ready to do some accounting. The cows will pay, he says! But lo and behold, some entries of his log are missing!
Farmer John is sure that he started his log on the day of a breakout. Help him determine the minimum and maximum number of breakouts that could have occurred during the logged period, over all sequences of events consistent with the remaining log entries.
The first line contains one integer n~(1 \le n \le 100) — the number of days Farmer John has been logging the breakout counter.
The second line contains space-separated integers. The -th integer is either , meaning that the log entry for day is missing, or a non-negative integer a_i~(0 \le a_i \le 100), meaning that on day the counter read a_i.
If no sequence of events is consistent with Farmer John's partial log and with the fact that the cows definitely broke out of the barn on the morning of day , print a single integer . Otherwise, print two space-separated integers and , where and are the minimum and maximum numbers of breakouts, respectively, over all consistent sequences of events.
Example 1
In this example, we can deduce that a breakout must have occurred on day . Since a breakout also occurred on day , the only remaining uncertainty is whether a breakout occurred on day . Hence, the total number of breakouts is either or .