Midilinga i Corrompecolon han sigut expulsats de la guild del WoW "Enigma", per raons que oscil·len entre "Difamador Principal" i "Dejar tirada a la hermandad en plena raid de Molten Core". Però no estan disposats a rendir-se tan fàcilment! Volen saber quanta gent queda dintre per determinar si tenen raiders suficients per muntar una raid decent i, amb sort, demostrar que la guild es morirà sense ells.

Tenen un talp dintre de la guild: "Milka", un jugador lleial que els segueix informant cada dia de quants jugadors hi ha... quan se'n recorda, que no és sempre perquè també juga a altres jocs i se'n oblida.

La guild "Enigma" ha estat operativa durant un període de N (1 ≤ N ≤ 200,000) dies, i tenia Pi (1 ≤ Pi ≤ 10⁶) jugadors al final del dia i.

Al final del primer dia, hi havia un sol jugador (P1 = 1) - el Guild Master, que va crear la guild sol. En cada dia posterior i (2 ≤ i ≤ N), és possible que el Guild Master hagi expulsat a tots els jugadors al matí per "Difamar" o "Ninjalooter". Passi el que passi, una persona nova sempre s'uneix a la guild a la tarda (perquè el Guild Master és un reclutador incansable que spammeja la Imserso constantment).

En altres paraules, si hi va haver expulsions el dia i, aleshores Pi = 1, i si no hi va haver expulsions, Pi = Pi del dia anterior + 1

Milka ha fet el seu millor esforç per fer seguiment i ha creat una llista d'observacions O1..N (0 ≤ Oi ≤ 10⁶). Si Oi = 0, aleshores Milka no té ni idea de quants jugadors tenia la guild al final del dia i. En cas contrari, si Oi > 0, aleshores Milka creu que la guild tenia exactament Oi jugadors al final del dia i (és a dir, que Pi = Oi).

Midilinga i Corrompecolon ara volen utilitzar les observacions de Milka per determinar quants cops el Guild Master ha expulsat gent de la guild. A causa dels forats en les observacions de Milka, pot haver-hi múltiples seqüències d'esdeveniments que siguin consistents amb elles, així que estan interessats tant en el mínim com en el màxim nombre d'expulsions que podrien haver tingut lloc durant els dies 2..N. També és possible que les observacions de Milka siguin inconsistents amb qualsevol seqüència possible d'esdeveniments (perquè és un troll).

Entrada

La primera línia conté un sol enter, N.

N línies segueixen, la i-èsima conté un sol enter, Oi, per i = 1..N.

Sortida

Mostra dos enters, el nombre mínim i màxim possible de dies on hi ha expulsions, o el sol enter −1 si és impossible que les observacions de Milka siguin precises.

Exemple d'Entrada

6
1
0
0
0
3
0

Exemple de Sortida

1 3

Explicació

Dies observats: [1, ?, ?, ?, 3, ?]

Mínim (1 expulsió): És possible que només hi hagués expulsions un sol dia. Per exemple: els dies 2, 3 i 4 no hi ha expulsions (creixement natural), però al dia 3 hi ha expulsions massives que deixen la guild amb 0 membres (1 al final del dia, ja que entra un nou jugador), i després tornen a créixer fins arribar als 3 observats al dia 5.

Màxim (3 expulsions): És possible que hi haguessin expulsions en 3 dies diferents. El Guild Master podria haver expulsat gent els dies 2, 3 i 6, sempre deixant 0 jugadors abans que arribés el nou recluta diari (i per tant, acabant el dia amb un jugador).

Exemple d'Entrada 2

3
1
0
4

Exemple de Sortida 2

-1

Explicació 2

Dies observats: [1, ?, 4]

Impossible! Al dia 3, com a màxim podrien haver-hi 3 jugadors (creixement natural sense expulsions des del dia 1). No hi ha manera d'arribar a 4 jugadors al dia 3, així que les observacions de Milka són incorrectes.