P1711 [USACO18FEB] Taming the Herd B

Early one morning, Farmer John was woken up by the sound of cracking wood. It was the cows again—they escaped from the barn! Farmer John is tired of the cows escaping in the morning, and he has had enough: it is time to take tough measures. He nailed a counter to the wall of the barn to track how many days have passed since the last escape. So if an escape happens on some morning, the counter is $0$ on that day; if the most recent escape was $3$ days ago, the counter reads $3$. Farmer John carefully recorded the counter reading for every day. By the end of the year, Farmer John wants to do some statistics. He says, you cows will pay the price! However, unexpectedly, some entries in his records were lost! Farmer John is sure that he started recording on a day when an escape happened. Please help him determine, among all escape event sequences consistent with the remaining record entries, based on the time covered by the records, the minimum and maximum possible number of escapes.

The first line contains an integer $N$ ($1\le N\le 100$), the number of days that have passed since Farmer John started counting using the escape counter. The second line contains $N$ space-separated integers. The $i$-th integer is $-1$, meaning the record for day $i$ is missing, or a non-negative integer $a_i$ (not exceeding $100$), meaning that on day $i$ the counter value was $a_i$.

If there is no event sequence consistent with Farmer John’s remaining records and the fact that the cows escaped on the morning of day $1$, output a single integer $-1$. Otherwise, output two space-separated integers $m$ and $M$, where $m$ is the minimum number of escapes among all event sequences, and $M$ is the maximum number of escapes.

In this sample, we can infer that an escape must have happened on day $3$. We already know that an escape also happened on day $1$, so the only remaining uncertainty is whether an escape happened on day $2$. Therefore, the total number of escapes is between $2$ and $3$. Translated by ChatGPT 5