P12630 [ICPC 2025 NAC] SLA Tomography

立体光刻（SLA）是一种 3D 打印技术，通过激光逐层将液态材料固化成固体物体。在本问题中，我们将考虑 SLA 的二维简化版本，其中打印对象的设计可以表示为一个由 $\texttt{\#}$ 和 $\texttt{.}$ 字符组成的矩形网格，$\texttt{\#}$ 表示被对象占据的网格单元，$\texttt{.}$ 表示空白区域。例如，以下是一个 $4 \times 8$ 的设计： ``` ..#..... ..#..#.. #.#.##.. #.#####. ``` 设计不必由单个连通块组成，但除了设计最底行的 $\texttt{\#}$ 单元外，**每个 $\texttt{\#}$ 单元必须由正下方的另一个 $\texttt{\#}$ 单元支撑**。 使用 SLA 打印对象的过程是逐层进行的，从最底行开始。首先，该行的所有单元都被液态光敏树脂覆盖。然后激光扫描该行，将所有 $\texttt{\#}$ 单元的树脂固化成固体，跳过所有 $\texttt{.}$ 单元。接着，最左侧 $\texttt{\#}$ 左侧和最右侧 $\texttt{\#}$ 右侧的多余液态树脂会流走，其他液态树脂则会被困住。（如果某行没有 $\texttt{\#}$ 单元——这种情况只可能发生在设计顶部附近，当对象已完全打印时——该行的所有液态树脂都会流走。）然后对每一后续行重复此过程。对于上面的设计，打印完成后，所有标有 $\sim$ 字符的单元中会残留树脂： ``` ..#..... ..#~~#.. #~#~##.. #~#####. ``` 在手动吸除对象上残留的树脂时，你开始思考：仅通过知道打印后设计每一行残留的液态树脂量，能还原出原始设计的多少信息？对于上述设计，每一行（从设计顶部开始）的残留树脂量分别为 $0$、$2$、$2$、$1$。其他设计也可能具有相同的残留树脂特征；例如： ``` .... #..# #..# #.## ``` 给定每一行（从顶行开始）残留液态树脂单元的数量列表，输出满足这些残留量的最窄对象设计的宽度。如果不存在这样的设计，输出 $\texttt{impossible}$。

第一行输入包含一个整数 $N$（$1 \leq N \leq 10^5$），表示对象设计的行数。 接下来 $N$ 行，每行包含一个整数 $x$（$0 \leq x \leq 10^9$），表示期望对象设计每一行（从顶行到底行）的残留液态树脂单元数量。 至少有一行的残留液态树脂单元数量大于零。

输出满足输入残留量的最窄对象设计的宽度（列数）。（"最窄"指列数尽可能少。）如果不存在这样的设计，输出 $\texttt{impossible}$。

样例输入 1 对应上述示例。样例输入 2 的一个最窄可能设计为： ``` #....#..... ######..... ######....# ``` 翻译由 DeepSeek V3 完成