Stereolithography (SLA) 是一种通过激光将液态材料硬化成固体对象的 3D 打印技术。在这个问题中，我们将考虑 SLA 的一个二维简化版本，其中要打印的对象的形状可以表示为一个矩形网格，由 '#' 和 '.' 字符组成，其中 '#' 代表对象占据的网格单元，'.' 代表空格。例如，这是一个 4 × 8 的设计：

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

一个设计不必由一个连通块组成，但除了设计最底行的 '#' 单元格外，每个 '#' 单元格必须由其正下方的另一个 '#' 单元格支撑。

使用 SLA 打印对象时，过程是逐层进行的，从最底行开始。首先，该行的所有单元格都浸入液态光敏树脂中。然后，激光扫描该行，将所有 '#' 单元格中的树脂硬化成固体，并跳过所有 '.' 单元格。接着，最左边的 '#' 左侧和最右边的 '#' 右侧的剩余液体会排干。其他液体会滞留。 （如果该行没有 '#' 单元格——这只可能发生在设计接近顶部、对象已完全打印的行——则该行的所有液体都会排干。）这个过程然后对每一行重复。对于上面的设计，打印完成后，滞留在单元格中的树脂用 '~' 字符表示，如下所示：

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

当手动吸取对象中剩余的树脂时，你会想知道：在打印后，仅凭每行剩余的液体量，能恢复多少原始设计？对于上面的设计，每行（从设计顶部开始）剩余树脂的量是 0, 2, 2, 1。其他设计也有相同的剩余树脂指纹；例如：

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

给定一个列表，其中包含每行（从顶部行开始）剩余的液体单元格数量，打印出满足这些数量的、最窄的对象设计的宽度（列数）。如果不存在这样的设计，则打印 impossible。

输入格式

输入的第一行包含一个整数 $N$ ($1 \le N \le 10^5$)，表示对象设计的行数。接下来 $N$ 行，每行包含一个整数 $x$ ($0 < x \le 10^9$)，表示所需对象设计中每行剩余的液体树脂单元格数量（从上到下）。

至少有一行将包含至少一个剩余的液体单元格。

输出格式

打印出最窄的对象设计的宽度（列数），该设计的每行剩余的液体树脂单元格数量与输入匹配。（“最窄”意味着具有最小的可能列数。）如果不存在这样的设计，则打印 impossible。

样例

样例说明

样例输入 1 对应于上面的示例。对于样例输入 2，一个最窄可能的设计是：

....#.....

.....

....

样例 1

输入

4
0
2
2
1

输出

4

样例 2

输入

3
4
0
4

输出

11