立體光刻（Stereolithography，簡稱 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，一個最窄可能的設計為：

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