Stereolithographie (SLA) ist ein 3D-Druckverfahren, bei dem flüssiges Material mithilfe eines Lasers Schicht für Schicht zu einem festen Objekt ausgehärtet wird. In dieser Aufgabe betrachten wir eine 2D-Vereinfachung von SLA, bei der das Design des zu druckenden Objekts als rechteckiges Gitter aus den Zeichen # und . dargestellt werden kann, wobei # für eine vom Objekt belegte Gitterzelle und . für leeren Raum steht. Hier ist zum Beispiel ein $4 \times 8$-Design:

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

Ein Design muss nicht aus einem einzigen zusammenhängenden Teil bestehen, aber mit Ausnahme der #-Zellen in der untersten Zeile des Designs muss jede #-Zelle von einer anderen #-Zelle direkt darunter gestützt werden.

Das Drucken eines Objekts mittels SLA erfolgt schichtweise, beginnend mit der untersten Zeile. Zuerst werden alle Zellen der Zeile mit einem flüssigen lichtempfindlichen Harz geflutet. Dann fährt ein Laser über die Zeile, härtet das Harz in allen #-Zellen zu einem Festkörper aus und überspringt alle .-Zellen. Anschließend fließt die überschüssige Flüssigkeit links vom am weitesten links liegenden # und rechts vom am weitesten rechts liegenden # ab. Andere Flüssigkeit bleibt eingeschlossen. (Wenn es in der Zeile keine #-Zellen gibt — was nur in Zeilen nahe dem oberen Rand des Designs passieren kann, nachdem das Objekt vollständig gedruckt wurde — fließt die gesamte Flüssigkeit aus der Zeile ab.) Dieser Vorgang wiederholt sich dann für jede darauffolgende Zeile. Für das obige Design bleibt nach Abschluss des Druckvorgangs Harz in allen Zellen eingeschlossen, die unten mit einem ~-Zeichen markiert sind:

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

Während du das überschüssige Harz manuell aus dem Objekt absaugst, beginnst du dich zu fragen: Wie viel vom ursprünglichen Design lässt sich rekonstruieren, wenn man nur weiß, wie viel flüssiges Harz nach dem Drucken in jeder Zeile des Designs übrig geblieben ist? Für das obige Design beträgt die Menge an übrig gebliebenem Harz in jeder Zeile (beginnend am oberen Rand des Designs) $0, 2, 2, 1$. Andere Designs haben ebenfalls denselben Rest-Harz-Fingerabdruck, zum Beispiel:

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

Gegeben eine Liste darüber, wie viele Zellen an flüssigem Harz in jeder Zeile (beginnend mit der obersten Zeile) übrig bleiben, gib die Breite des schmalsten Objektdesigns aus, dessen Zeilen nach dem Drucken genau diese Mengen an flüssigem Harz enthalten würden. Falls kein solches Design existiert, gib impossible aus.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $N$ ($1 \le N \le 10^5$), die Anzahl der Zeilen im Objektdesign. Es folgen $N$ Zeilen, die jeweils eine einzelne ganze Zahl $x$ ($0 \le x \le 10^9$) enthalten — die Anzahl der Zellen mit übrig gebliebenem flüssigem Harz in jeder Zeile des gewünschten Objektdesigns (in der Reihenfolge von oben nach unten).

Mindestens eine Zeile enthält mindestens eine Zelle mit übrig gebliebenem flüssigem Harz.

Ausgabe

Gib die Breite (Anzahl der Spalten) des schmalsten Objektdesigns aus, dessen Anzahl an Zellen mit übrig gebliebenem flüssigem Harz in jeder Zeile mit der Eingabe übereinstimmt. („Schmalstes“ bedeutet mit der kleinstmöglichen Anzahl an Spalten.) Falls kein solches Design existiert, gib stattdessen impossible aus.

Beispiele

Eingabe 1

4
0
2
2
1

Ausgabe 1

4

Eingabe 2

3
4
0
4

Ausgabe 2

11

Hinweis

Beispieleingabe 1 entspricht dem obigen Beispiel. Ein schmalstmögliches Design für Beispieleingabe 2 ist:

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