In li-tô lập thể (Stereolithography — SLA) là một kỹ thuật in 3D dùng tia laser để làm đông cứng vật liệu lỏng thành vật thể rắn theo từng lớp một. Trong bài toán này, chúng ta sẽ xét một phiên bản đơn giản hóa 2D của SLA, trong đó thiết kế của vật thể đang được in có thể được biểu diễn dưới dạng một lưới chữ nhật gồm các ký tự # và ., với # biểu thị một ô lưới bị chiếm bởi vật thể và . là khoảng trống. Ví dụ, dưới đây là một thiết kế $4 \times 8$:

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

Một thiết kế không nhất thiết phải gồm một khối liên thông duy nhất, nhưng ngoại trừ các ô # ở hàng dưới cùng của thiết kế, mỗi ô # phải được đỡ bởi một ô # khác nằm ngay bên dưới nó.

Việc in một vật thể bằng SLA diễn ra theo từng lớp, bắt đầu từ hàng dưới cùng. Đầu tiên, tất cả các ô trong hàng được làm ngập bởi một loại nhựa lỏng nhạy sáng. Sau đó, tia laser quét qua hàng, làm đông cứng nhựa trong tất cả các ô # thành chất rắn và bỏ qua tất cả các ô .. Tiếp theo, phần chất lỏng dư thừa ở bên trái ô # ngoài cùng bên trái và ở bên phải ô # ngoài cùng bên phải sẽ thoát ra ngoài. Phần chất lỏng còn lại bị giữ kẹt bên trong. (Nếu không có ô # nào trong hàng — điều chỉ có thể xảy ra ở các hàng gần phía trên cùng của thiết kế, sau khi vật thể đã được in xong hoàn toàn — thì toàn bộ chất lỏng sẽ thoát hết khỏi hàng đó.) Quá trình này sau đó lặp lại cho từng hàng tiếp theo. Đối với thiết kế ở trên, sau khi quá trình in hoàn tất, nhựa vẫn bị kẹt lại trong tất cả các ô được đánh dấu bằng ký tự ~ dưới đây:

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

Trong lúc hút thủ công phần nhựa dư thừa ra khỏi vật thể, bạn bắt đầu tự hỏi: có thể khôi phục được bao nhiêu phần của thiết kế ban đầu nếu chỉ biết lượng nhựa lỏng còn sót lại ở mỗi hàng của thiết kế sau khi in? Đối với thiết kế ở trên, lượng nhựa còn sót lại ở mỗi hàng (tính từ đỉnh của thiết kế xuống) là $0, 2, 2, 1$. Các thiết kế khác cũng có cùng dấu vết nhựa dư thừa như vậy; ví dụ:

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

Cho danh sách số lượng ô nhựa lỏng còn sót lại ở mỗi hàng (bắt đầu từ hàng trên cùng), hãy in ra chiều rộng của thiết kế vật thể hẹp nhất mà các hàng của nó chứa đúng số lượng nhựa lỏng đó sau khi in. Nếu không tồn tại thiết kế như vậy, hãy in ra impossible.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $N$ ($1 \le N \le 10^5$), là số hàng trong thiết kế vật thể. $N$ dòng tiếp theo, mỗi dòng chứa một số nguyên duy nhất $x$ ($0 \le x \le 10^9$), là số ô nhựa lỏng còn sót lại ở mỗi hàng của thiết kế vật thể mong muốn (theo thứ tự từ trên xuống dưới).

Ít nhất một hàng sẽ có ít nhất một ô nhựa lỏng còn sót lại.

Dữ liệu ra

In ra chiều rộng (số cột) của thiết kế vật thể hẹp nhất có số lượng ô nhựa lỏng còn sót lại ở mỗi hàng khớp với dữ liệu vào. ("Hẹp nhất" có nghĩa là có số lượng cột nhỏ nhất có thể). Nếu không tồn tại thiết kế như vậy, hãy in ra impossible để thay thế.

Ví dụ

Dữ liệu vào 1

4
0
2
2
1

Dữ liệu ra 1

4

Dữ liệu vào 2

3
4
0
4

Dữ liệu ra 2

11

Ghi chú

Dữ liệu vào mẫu 1 tương ứng với ví dụ ở trên. Một thiết kế hẹp nhất có thể cho Dữ liệu vào mẫu 2 là:

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