La stéréolithographie (SLA) est une technique d'impression 3D permettant de durcir un matériau liquide en un objet solide, une couche à la fois, à l'aide d'un laser. Dans ce problème, nous considérons une simplification 2D de la SLA où le modèle de l'objet imprimé peut être représenté par une grille rectangulaire de caractères # et ., où # représente une cellule de la grille occupée par l'objet et . représente un espace vide. Par exemple, voici un modèle de taille $4 \times 8$ :

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

Un modèle n'est pas obligé d'être constitué d'un seul morceau connexe, mais à l'exception des cellules # situées sur la ligne la plus basse du modèle, chaque cellule # doit être soutenue par une autre cellule # située directement en dessous d'elle.

L'impression d'un objet par SLA procède couche par couche, en commençant par la ligne du bas. Tout d'abord, toutes les cellules de la ligne sont inondées d'une résine liquide photosensible. Ensuite, un laser balaie la ligne, durcissant la résine de toutes les cellules # en un solide et ignorant toutes les cellules .. Puis, le liquide restant à gauche du # le plus à gauche et à droite du # le plus à droite s'écoule. Le reste du liquide demeure piégé. (S'il n'y a aucune cellule # dans la ligne — ce qui ne peut se produire que pour des lignes proches du sommet du modèle, une fois l'objet entièrement imprimé — tout le liquide s'écoule de la ligne.) Ce processus se répète ensuite pour chaque ligne suivante. Pour le modèle ci-dessus, une fois l'impression terminée, de la résine reste piégée dans toutes les cellules marquées par un caractère ~ ci-dessous :

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

Tout en aspirant manuellement l'excédent de résine de l'objet, vous commencez à vous demander : quelle part du modèle original peut-on reconstituer en sachant uniquement quelle quantité de résine liquide reste dans chaque ligne du modèle après l'impression ? Pour le modèle ci-dessus, la quantité de résine restante dans chaque ligne (en partant du haut du modèle) est $0, 2, 2, 1$. D'autres modèles possèdent également la même empreinte de résine résiduelle ; par exemple :

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

Étant donné la liste du nombre de cellules de résine liquide restantes dans chaque ligne (en partant de la ligne du haut), affichez la largeur du modèle d'objet le plus étroit dont les lignes contiendraient ces quantités de résine liquide après l'impression. S'il n'existe aucun modèle de ce type, affichez impossible.

Entrée

La première ligne de l'entrée contient un seul entier $N$ ($1 \le N \le 10^5$), le nombre de lignes dans le modèle de l'objet. $N$ lignes suivent, contenant chacune un seul entier $x$ ($0 \le x \le 10^9$), le nombre de cellules de résine liquide restante dans chaque ligne du modèle d'objet souhaité (dans l'ordre du haut vers le bas).

Au moins une ligne contiendra au moins une cellule de résine liquide restante.

Sortie

Affichez la largeur (le nombre de colonnes) du modèle d'objet le plus étroit dont le nombre de cellules de résine liquide restante dans chaque ligne correspond à l'entrée. (« Le plus étroit » signifie ayant le plus petit nombre possible de colonnes.) S'il n'existe aucun modèle de ce type, affichez impossible à la place.

Exemples

Entrée 1

4
0
2
2
1

Sortie 1

4

Entrée 2

3
4
0
4

Sortie 2

11

Remarque

L'exemple d'entrée 1 correspond à l'exemple présenté dans l'énoncé. Un modèle le plus étroit possible pour l'exemple d'entrée 2 est :

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