Стереолитография (SLA) — лазердің көмегімен сұйық материалды қабат-қабатымен қатты объектіге айналдырып қатыратын 3D басып шығару технологиясы. Бұл есепте біз SLA технологиясының 2D жеңілдетілген нұсқасын қарастырамыз, мұнда басып шығарылатын объектінің дизайнын # және . таңбаларынан тұратын тікбұрышты тор ретінде көрсетуге болады, мұндағы # объектімен толтырылған тор ұяшығын, ал . бос кеңістікті білдіреді. Мысалы, міне $4 \times 8$ өлшемді дизайн:

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

Дизайн міндетті түрде бір ғана байланысқан бөліктен тұруы шарт емес, бірақ дизайнның ең төменгі қатарындағы # ұяшықтарын қоспағанда, әрбір # ұяшығын оның дәл астында орналасқан басқа бір # ұяшығы тіреп тұруы тиіс.

SLA көмегімен объектіні басып шығару ең төменгі қатардан бастап қабат-қабатымен жүреді. Алдымен қатардағы барлық ұяшықтар сұйық жарықсезгіш шайырмен толтырылады. Содан кейін лазер қатарды бойлай өтіп, барлық # ұяшықтарындағы шайырды қатты денеге айналдырып қатырады да, барлық . ұяшықтарын өткізіп жібереді. Содан соң ең сол жақтағы # таңбасының сол жағындағы және ең оң жақтағы # таңбасының оң жағындағы артық сұйықтық ағып кетеді. Басқа сұйықтық ішінде қамалып қалады. (Егер қатарда # ұяшықтары мүлдем болмаса — бұл тек объект толығымен басып шығарылғаннан кейін, дизайнның жоғарғы жағына жақын қатарларда ғана болуы мүмкін — онда қатардағы барлық сұйықтық ағып кетеді.) Бұл процесс келесі әрбір қатар үшін қайталанады. Жоғарыдағы дизайн үшін басып шығару аяқталғаннан кейін, шайыр төменде ~ таңбасымен белгіленген барлық ұяшықтарда қамалып қалады:

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

Объектіден қалған шайырды қолмен сорып алып жатып, сіз ойлана бастайсыз: басып шығарғаннан кейін дизайнның әр қатарында қанша сұйық шайыр қалғанын ғана біле отырып, бастапқы дизайнның қанша бөлігін қалпына келтіруге болады? Жоғарыдағы дизайн үшін әр қатарда (дизайнның ең жоғарғы жағынан бастап) қалған шайыр мөлшері — $0, 2, 2, 1$. Басқа дизайндарда да қалдық шайырдың дәл осындай ізі болуы мүмкін; мысалы:

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

Әр қатарда (ең жоғарғы қатардан бастап) қанша ұяшық сұйық шайыр қалғаны туралы тізім берілген, басып шығарғаннан кейін қатарларында дәл сондай мөлшерде сұйық шайыр қалатын ең енсіз объект дизайнының енін шығарыңыз. Егер мұндай дизайн болмаса, impossible деп шығарыңыз.

Кіріс деректер

Кіріс деректердің бірінші жолында бір бүтін сан $N$ ($1 \le N \le 10^5$) — объект дизайнындағы қатарлар саны берілген. Одан кейінгі $N$ жолдың әрқайсысында бір бүтін сан $x$ ($0 \le x \le 10^9$) — қажетті объект дизайнының әр қатарындағы қалған сұйық шайыр ұяшықтарының саны (жоғарыдан төмен қарай ретімен) берілген.

Кем дегенде бір қатарда кем дегенде бір ұяшық қалған сұйық шайыр болады.

Шығыс деректер

Әр қатардағы қалған сұйық шайыр ұяшықтарының саны кіріс деректерге сәйкес келетін ең енсіз объект дизайнының енін (бағандар санын) шығарыңыз. («Ең енсіз» дегеніміз мүмкін болатын ең аз бағандар санына ие дегенді білдіреді). Егер мұндай дизайн болмаса, оның орнына impossible деп шығарыңыз.

Мысалдар

Кіріс деректер 1

4
0
2
2
1

Шығыс деректер 1

4

Кіріс деректер 2

3
4
0
4

Шығыс деректер 2

11

Ескертпе

1-мысал жоғарыдағы мысалға сәйкес келеді. 2-мысал үшін мүмкін болатын ең енсіз дизайндардың бірі:

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