Стереолитография (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

Примечание

Первый пример соответствует примеру из условия. Одна из возможных самых узких схем для второго примера выглядит так:

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