광경화성 수지 조형 방식(Stereolithography, SLA)은 레이저를 이용해 액체 재료를 한 층씩 경화시켜 고체 물체를 만드는 3D 프린팅 기술입니다. 이 문제에서는 출력할 물체의 설계도를 #과 . 문자로 이루어진 직사각형 격자로 나타낼 수 있는 2D 단순화 버전의 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

참고

예제 입력 1은 본문의 예시와 일치합니다. 예제 입력 2에 대해 가능한 가장 폭이 좁은 설계도 중 하나는 다음과 같습니다.

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