Counting Escapes

Farmer John has installed a counter on his barn wall to record the number of days since the last cow escape. On an escape day (the morning a cow escapes), the counter resets to \(0\). On a day when no escape occurs, the counter increases by 1 compared to the previous day.

Farmer John began recording on an escape day, so the counter on day 1 is \(0\). Unfortunately, some of the recorded entries were lost. You are given a sequence of \(n\) days. For each day, the record is either a nonnegative integer or missing (denoted by \(-1\)). Your task is to determine, over all valid event sequences that are consistent with the remaining records and the counter rule, the minimum and maximum number of escape events that could have occurred.

The counter follows the recurrence:

[ a_1 = 0, \quad\text{and for } i > 1, \quad a_i = \begin{cases} 0, &\text{if an escape occurs on day } i,\ a_{i-1}+1, &\text{otherwise.} \end{cases} ]

A record entry is valid if the computed value equals the given value when it is not missing (i.e. not equal to \(-1\)).

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) (the number of days). The second line contains \(n\) space-separated integers representing the logged counter readings. A value of \(-1\) indicates that the record for that day is missing.

outputFormat

Output two space-separated integers: the minimum and maximum number of escape events that could have occurred over the \(n\) days, consistent with the remaining records.

sample

5
0 1 2 0 1

2 2