La stereolitografia (SLA) è una tecnica di stampa 3D per indurire un materiale liquido in un oggetto solido uno strato alla volta utilizzando un laser. In questo problema considereremo una semplificazione 2D della SLA in cui il modello dell'oggetto da stampare può essere rappresentato come una griglia rettangolare di caratteri # e ., dove # rappresenta una cella della griglia occupata dall'oggetto e . è uno spazio vuoto. Ad esempio, ecco un modello $4 \times 8$:

..#.....
..#..#..
#.#.##..
#.#####.

Un modello non deve necessariamente consistere in un unico pezzo connesso, ma a eccezione delle celle # sulla riga inferiore del modello, ogni cella # deve essere sostenuta da un'altra cella # direttamente sotto di essa.

La stampa di un oggetto tramite SLA procede strato per strato, partendo dalla riga inferiore. Prima tutte le celle della riga vengono inondate con una resina liquida fotosensibile. Poi un laser scansiona la riga, indurendo la resina in tutte le celle # trasformandola in solido e saltando tutte le celle .. Successivamente, il liquido rimasto a sinistra del # più a sinistra e a destra del # più a destra defluisce. L'altro liquido rimane intrappolato. (Se non ci sono celle # nella riga — cosa che può accadere solo per le righe vicine alla parte superiore del modello, dopo che l'oggetto è stato completamente stampato — tutto il liquido defluisce dalla riga.) Questo processo si ripete poi per ciascuna riga successiva. Per il modello sopra, una volta completata la stampa, la resina rimane intrappolata in tutte le celle contrassegnate con il carattere ~ qui sotto:

..#.....
..#~~#..
#~#~##..
#~#####.

Mentre aspiri manualmente la resina rimasta dall'oggetto, inizi a chiederti: quanto del modello originale può essere recuperato sapendo solo quanta resina liquida è rimasta in ciascuna riga del modello dopo la stampa? Per il modello sopra, la quantità di resina rimasta in ciascuna riga (partendo dalla cima del modello) è $0, 2, 2, 1$. Anche altri modelli hanno la stessa impronta di resina residua; ad esempio:

....
#..#
#..#
#.##

Data una lista di quante celle di resina liquida rimangono in ciascuna riga (partendo dalla riga superiore), stampa la larghezza del modello di oggetto più stretto le cui righe conterrebbero tali quantità di resina liquida dopo la stampa. Se non esiste alcun modello del genere, stampa impossible.

Dati di ingresso

La prima riga di ingresso contiene un singolo intero $N$ ($1 \le N \le 10^5$), il numero di righe nel modello dell'oggetto. Seguono $N$ righe, ciascuna contenente un singolo intero $x$ ($0 \le x \le 10^9$), il numero di celle di resina liquida residua in ciascuna riga del modello di oggetto desiderato (in ordine dall'alto verso il basso).

Almeno una riga avrà almeno una cella residua di resina liquida.

Dati di uscita

Stampa la larghezza (numero di colonne) nel modello di oggetto più stretto il cui numero di celle di resina liquida residua in ciascuna riga corrisponde all'ingresso. ("Più stretto" significa avente il minor numero possibile di colonne). Se non esiste alcun modello del genere, stampa invece impossible.

Esempi

Dati di ingresso 1

4
0
2
2
1

Dati di uscita 1

4

Dati di ingresso 2

3
4
0
4

Dati di uscita 2

11

Note

L'esempio di ingresso 1 corrisponde all'esempio sopra. Un modello il più stretto possibile per l'esempio di ingresso 2 è:

#....#.....
######.....
######....#