Stereolitografia (SLA) on 3D-tulostustekniikka, jossa nestemäinen materiaali kovetetaan kiinteäksi esineeksi kerros kerrallaan laserin avulla. Tässä tehtävässä tarkastelemme SLA:n kaksiulotteista yksinkertaistusta, jossa tulostettavan esineen malli voidaan esittää merkeistä # ja . koostuvana suorakulmaisena ruudukkona, missä # kuvaa esineen täyttämää ruudukon solua ja . on tyhjää tilaa. Esimerkiksi tässä on $4 \times 8$-kokoinen malli:

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

Mallin ei tarvitse koostua yhdestä yhtenäisestä kappaleesta, mutta lukuun ottamatta mallin alimmalla rivillä olevia #-soluja jokaisen #-solun täytyy olla suoraan sen alapuolella olevan toisen #-solun tukema.

Esineen tulostaminen SLA-tekniikalla etenee kerros kerrokselta alimmasta rivistä alkaen. Ensin kaikki rivin solut peitetään nestemäisellä valoherkällä hartsilla. Sitten laser pyyhkäisee rivin yli, kovettaa kaikkien #-solujen hartsin kiinteäksi aineeksi ja ohittaa kaikki .-solut. Tämän jälkeen vasemmanpuoleisimman #-solun vasemmalla puolella ja oikeanpuoleisimman #-solun oikealla puolella oleva ylimääräinen neste valuu pois. Muu neste jää loukkuun. (Jos rivillä ei ole yhtään #-solua — mikä voi tapahtua vain mallin yläosan lähellä olevilla riveillä sen jälkeen, kun esine on jo kokonaan tulostettu — kaikki neste valuu pois riviltä.) Tämä prosessi toistuu sitten jokaiselle seuraavalle riville. Yllä olevassa mallissa tulostuksen valmistuttua hartsia jää loukkuun kaikkiin alla merkillä ~ merkittyihin soluihin:

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

Imiessäsi ylimääräistä hartsia esineestä käsin alat pohtia: kuinka paljon alkuperäisestä mallista voidaan päätellä, jos tiedetään vain se, kuinka paljon nestemäistä hartsia kuhunkin mallin riviin on jäänyt tulostuksen jälkeen? Yllä olevassa mallissa jäljelle jääneen hartsin määrä kullakin rivillä (mallin yläosasta alkaen) on $0, 2, 2, 1$. Muillakin malleilla on sama jäännöshartsin sormenjälki; esimerkiksi:

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

Kun annetaan lista siitä, kuinka monta solua nestemäistä hartsia kullakin rivillä (ylimmästä rivistä alkaen) on jäljellä, tulosta kapeimman sellaisen esinemallin leveys, jonka riveille jäisi kyseiset määrät nestemäistä hartsia tulostuksen jälkeen. Jos tällaista mallia ei ole olemassa, tulosta impossible.

Syöte

Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $N$ ($1 \le N \le 10^5$), joka on esinemallin rivien lukumäärä. Seuraa $N$ riviä, joista jokainen sisältää yhden kokonaisluvun $x$ ($0 \le x \le 10^9$), joka on jäljelle jääneiden nestemäisen hartsin solujen lukumäärä halutun esinemallin kullakin rivillä (järjestyksessä ylhäältä alas).

Vähintään yhdellä rivillä on vähintään yksi jäljelle jäänyt nestemäisen hartsin solu.

Tuloste

Tulosta leveys (sarakkeiden lukumäärä) kapeimmassa esinemallissa, jossa jäljelle jääneiden nestemäisen hartsin solujen lukumäärä kullakin rivillä vastaa syötettä. ("Kapein" tarkoittaa mallia, jossa on pienin mahdollinen määrä sarakkeita). Jos tällaista mallia ei ole olemassa, tulosta sen sijaan impossible.

Esimerkit

Syöte 1

4
0
2
2
1

Tuloste 1

4

Syöte 2

3
4
0
4

Tuloste 2

11

Huomautus

Esimerkkisyöte 1 vastaa yllä olevaa esimerkkiä. Yksi kapeimmista mahdollisista malleista esimerkkisyötteelle 2 on:

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