Domare la mandria#10407
Presto al mattino, contadino John si è svegliato per lo schianto di un albero che si spezzava. Erano le mucche — stavano scappando di nuovo dal fienile!
Contadino John era stufo morto delle fughe mattutine delle mucche e decise che ne aveva abbastanza: era ora di prendere misure drastiche. Inchiodò alla parete del fienile un contatore che mostrava il numero di giorni trascorsi dall'ultima fuga. Quindi, se una fuga avveniva al mattino, quel giorno il contatore mostrava ; se l'ultima fuga era avvenuta giorni prima, il contatore mostrava . Ogni giorno il contadino John annotava scrupolosamente le letture del contatore nel suo registro.
È arrivata la fine dell'anno, e il contadino John è pronto a tirare le somme. Le mucche pagheranno per tutto, dice lui! Ma c'è un problema — alcune voci nel suo registro sono andate perse!
Il contadino John è sicuro di aver iniziato a tenere il registro proprio nel giorno di una fuga. Aiutalo a determinare il numero minimo e massimo di fughe che potrebbero essere avvenute durante il periodo in cui ha tenuto il registro, tra tutte le sequenze di eventi compatibili con le voci sopravvissute.
Nella prima riga è dato un singolo numero intero n~(1 \le n \le 100) — il numero di giorni durante i quali il contadino John ha registrato le letture del contatore delle fughe.
Nella seconda riga sono dati numeri interi separati da spazi. L'-esimo numero è uguale a , il che significa che la voce per il giorno è mancante, oppure a un numero intero non negativo a_i~(0 \le a_i \le 100), il che significa che nel giorno il contatore mostrava a_i.
Se non esiste alcuna sequenza di eventi compatibile con il registro parzialmente conservato del contadino John e con il fatto che al mattino del giorno le mucche sono sicuramente scappate dal fienile, stampa un singolo numero . Altrimenti, stampa separati da uno spazio due numeri interi e , dove e sono rispettivamente il numero minimo e massimo di fughe tra tutte le sequenze di eventi compatibili.
Esempio 1