Стереолітографія (SLA) — це технологія 3D-друку для затвердіння рідкого матеріалу в твердий об'єкт шар за шаром за допомогою лазера. У цій задачі ми розглянемо двовимірне спрощення SLA, де проєкт об'єкта, що друкується, можна подати як прямокутну сітку із символів # та ., де # позначає клітинку сітки, зайняту об'єктом, а . — порожній простір. Наприклад, ось проєкт розміром $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

Примітка

Перший приклад відповідає прикладу, наведеному вище. Один із найвужчих можливих проєктів для другого прикладу має вигляд:

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