Stereólítógrafía (SLA) er þrívíddarprentunartækni til að herða fljótandi efni í fastan hlut eitt lag í einu með leysi. Í þessu verkefni munum við skoða tvívíða einföldun á SLA þar sem hægt er að tákna hönnun hlutarins sem verið er að prenta sem rétthyrnt grindanet af táknunum # og ., þar sem # táknar reit í grindinni sem hluturinn tekur og . er autt rými. Til dæmis er hér $4 \times 8$ hönnun:

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

Hönnun þarf ekki að samanstanda af einu samfelldu stykki, en að undanskildum #-reitum í neðstu röð hönnunarinnar verður sérhver #-reitur að vera studdur af öðrum #-reit beint fyrir neðan hann.

Prentun á hlut með SLA fer fram lag fyrir lag, byrjað á neðstu röðinni. Fyrst er öllum reitum í röðinni drekkt í fljótandi ljósnæmu plastefni. Síðan sópar leysir yfir röðina, herðir plastefnið í öllum #-reitum í fast efni og sleppir öllum .-reitum. Því næst rennur afgangsvökvi vinstra megin við #-reitinn sem er lengst til vinstri og hægra megin við #-reitinn sem er lengst til hægri í burtu. Annar vökvi verður innlyksa. (Ef engir #-reitir eru í röðinni — sem getur aðeins gerst í röðum nálægt efri hluta hönnunarinnar, eftir að hluturinn hefur verið fullprentaður — rennur allur vökvi í burtu úr röðinni.) Þetta ferli endurtekur sig síðan fyrir hverja röð þar á eftir. Fyrir hönnunina hér að ofan, eftir að prentun er lokið, verður plastefni innlyksa í öllum reitunum sem merktir eru með ~-tákni hér að neðan:

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

Á meðan þú sýgur afgangsplastefnið handvirkt úr hlutnum ferðu að velta fyrir þér: hversu mikið af upprunalegu hönnuninni er hægt að endurheimta með því einu að vita hversu mikið fljótandi plastefni er eftir í hverri röð hönnunarinnar eftir prentun? Fyrir hönnunina hér að ofan er magn afgangsplastefnis í hverri röð (byrjað efst í hönnuninni) $0, 2, 2, 1$. Aðrar hannanir hafa einnig sama fingrafar afgangsplastefnis; til dæmis:

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

Gefinn er listi yfir hversu margir reitir af fljótandi plastefni eru eftir í hverri röð (byrjað á efstu röðinni), prentið breidd mjóstu hönnunar hlutar sem myndi innihalda þetta magn af fljótandi plastefni í hverri röð eftir prentun. Ef engin slík hönnun er til skal prenta impossible.

Inntak

Fyrsta línan í inntakinu inniheldur eina heiltölu $N$ ($1 \le N \le 10^5$), fjölda raða í hönnun hlutarins. Þar á eftir fylgja $N$ línur, þar sem hver lína inniheldur eina heiltölu $x$ ($0 \le x \le 10^9$), fjölda reita af afgangs fljótandi plastefni í hverri röð hinnar æskilegu hönnunar hlutarins (í röðinni ofan frá og niður).

Að minnsta kosti ein röð mun hafa að minnsta kosti einn reit af afgangs fljótandi plastefni.

Úttak

Prentið breiddina (fjölda dálka) í mjóstu hönnun hlutar þar sem fjöldi reita af afgangs fljótandi plastefni í hverri röð passar við inntakið. („Mjóst“ þýðir að hafa minnsta mögulega fjölda dálka). Ef engin slík hönnun er til skal prenta impossible í staðinn.

Dæmi

Inntak 1

4
0
2
2
1

Úttak 1

4

Inntak 2

3
4
0
4

Úttak 2

11

Athugasemd

Sýnidæmi 1 samsvarar dæminu hér að ofan. Ein mjósta mögulega hönnun fyrir sýnidæmi 2 er:

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