题面翻译：给定一个长度为 n n n 的序列 a a a，其中有一些元素未知，用 − 1 -1 −1 表示，现在要将数组 a a a补充完整，即将 a a a 中所有的 − 1 -1 −1 替换成一个小于等于 1 0 9 10^9 109 的正整数，使得对于任意一个 1 ≤ i < n 1\leq i<n 1≤i<n，都有 a i = ⌊ a i + 1 2 ⌋ a_i=\left\lfloor\frac{a_{i+1}}{2}\right\rfloor ai=⌊2ai+1⌋ 或者 a i + 1 = ⌊ a i 2 ⌋ a_{i+1}=\left\lfloor\frac{a_i}{2}\right\rfloor ai+1=⌊2ai⌋。如果存在合法的方案，输出填充后的数组，否则输出 − 1 -1 −1。
数据范围： n ≤ 2 ⋅ 1 0 5 n\leq2\cdot10^5 n≤2⋅105，只能接受线性算法。
Part 2：算法分析
典型构造题。
首先特判，如果 a a a 中所有元素都未知，那么就 1 1 1 和 2 2 2 交替输出。
由于前缀和后缀的 − 1 -1 −1 都很好处理，并且对中间没有影响，先将他们特别处理。具体的，以前缀为例，假设 a 1 a_1 a1 到 a i a_i ai 均为 − 1 -1 −1，且 a i + 1 a_{i+1} ai+1 不是 − 1 -1 −1，是已知的，那么将 1 1 1 到 i i i 中所有与 i + 1 i+1 i+1奇偶性相同的赋值为 a i + 1 a_{i+1} ai+1，其余赋值为 a i + 1 × 2 a_{i+1}\times 2 ai+1×2。
对于中间，每个连续的 − 1 -1 −1 组成的段是独立的，可分别处理。假设现在处理的是 a u a_u au 到 a v a_v av 这个段，我们的目标就是通过 v − u + 2 v-u+2 v−u+2 次乘 2 2 2、除以 2 2 2 的操作让 a u − 1 a_{u-1} au−1 变成 a v + 1 a_{v+1} av+1。也就是说 a u − 1 ≠ − 1 a_{u-1}\neq-1 au−1=−1， a u a_u au 到 a v a_v av 都是 − 1 -1 −1， a v + 1 ≠ − 1 a_{v+1}\neq-1 av+1=−1。根据题面分析，其实说 a i a_i ai 和 a i + 1 a_{i+1} ai+1 满足条件，实际上就是说它们在由 1 1 1 到 n n n 编号的节点组成的完全二叉树上是相邻的。因此， a u − 1 a_{u-1} au−1 通过一些操作变成 a v + 1 a_{v+1} av+1，就相当于在这棵完全二叉树上找到一个从 a u − 1 a_{u-1} au−1 走到 a v + 1 a_{v+1} av+1 的长度等于 v − u + 2 v-u+2 v−u+2 的路径。
如何找这条路径呢？显然，只要找出两个节点的 LCA，按照 a u − 1 a_{u-1} au−1 到 LCA 再到 a v + 1 a_{v+1} av+1 的顺序走就能得出最短的一条路径。至于怎么使它加长，就可以直接在某个点上，比如 LCA，不断地乘 2 2 2、除以 2 2 2 就可以了。当然，如果奇偶性不对，或者最短的长度也不够，自然不行。
