Turtle and an Incomplete Sequence
Contest: Codeforces Round 949 (Div. 2)
Difficulty rating: 1800
Tags: bitmasks, brute force, constructive algorithms, greedy, implementation, math

Turtle was playing with a sequence $$$a_1, a_2, \ldots, a_n$$$ consisting of positive integers. Unfortunately, some of the integers went missing while playing.

Now the sequence becomes incomplete. There may exist an arbitrary number of indices $$$i$$$ such that $$$a_i$$$ becomes $$$-1$$$. Let the new sequence be $$$a'$$$.

Turtle is sad. But Turtle remembers that for every integer $$$i$$$ from $$$1$$$ to $$$n - 1$$$, either $$$a_i = \left\lfloor\frac{a_{i + 1}}{2}\right\rfloor$$$ or $$$a_{i + 1} = \left\lfloor\frac{a_i}{2}\right\rfloor$$$ holds for the original sequence $$$a$$$.

Turtle wants you to help him complete the sequence. But sometimes Turtle makes mistakes, so you need to tell him if you can't complete the sequence.

Formally, you need to find another sequence $$$b_1, b_2, \ldots, b_n$$$ consisting of positive integers such that:

- For every integer $$$i$$$ from $$$1$$$ to $$$n$$$, if $$$a'_i \ne -1$$$, then $$$b_i = a'_i$$$.
- For every integer $$$i$$$ from $$$1$$$ to $$$n - 1$$$, either $$$b_i = \left\lfloor\frac{b_{i + 1}}{2}\right\rfloor$$$ or $$$b_{i + 1} = \left\lfloor\frac{b_i}{2}\right\rfloor$$$ holds.
- For every integer $$$i$$$ from $$$1$$$ to $$$n$$$, $$$1 \le b_i \le 10^9$$$.

If there is no sequence $$$b_1, b_2, \ldots, b_n$$$ that satisfies all of the conditions above, you need to report $$$-1$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the sequence.

The second line of each test case contains $$$n$$$ integers $$$a'_1, a'_2, \ldots, a'_n$$$ ($$$a'_i = -1$$$ or $$$1 \le a'_i \le 10^8$$$) — the elements of the sequence $$$a'$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if there is no sequence $$$b_1, b_2, \ldots, b_n$$$ that satisfies all of the conditions, output a single integer $$$-1$$$.

Otherwise, output $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ — the elements of the sequence $$$b_1, b_2, \ldots, b_n$$$ you find. The sequence should satisfy that $$$1 \le b_i \le 10^9$$$ for every integer $$$i$$$ from $$$1$$$ to $$$n$$$. If there are multiple answers, print any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$[4, 2, 1, 2, 1, 2, 1, 3]$$$ can also be the answer, while $$$[4, 2, 5, 10, 5, 2, 1, 3]$$$ and $$$[4, 2, 1, 2, 1, 2, 1, 4]$$$ cannot.

In the second test case, $$$[1, 2, 5, 2]$$$ can also be the answer.

From the fourth to the sixth test cases, it can be shown that there is no answer, so you should output $$$-1$$$.

Example input:
9
8
-1 -1 -1 2 -1 -1 1 -1
4
-1 -1 -1 -1
6
3 -1 -1 -1 9 -1
4
-1 5 -1 6
4
2 -1 -1 3
4
1 2 3 4
2
4 2
5
-1 3 -1 3 6
13
-1 -1 3 -1 -1 -1 -1 7 -1 -1 3 -1 -1

Example output:
4 9 4 2 4 2 1 2
7 3 6 13
3 1 2 4 9 18
-1
-1
-1
4 2
6 3 1 3 6
3 1 3 1 3 7 3 7 3 1 3 1 3

Editorial:
Handle the special case where all elements are $$$-1$$$ first.
Consider extracting all positions where the values are not $$$-1$$$, denoted as $$$c_1, c_2, \ldots, c_k$$$. The segments $$$[1, c_1 - 1]$$$ and $$$[c_k + 1, n]$$$ with $$$-1$$$s are easy to handle by repeatedly multiplying and dividing by $$$2$$$. It's easy to see that the constructions of the segments $$$[c_1 + 1, c_2 - 1], [c_2 + 1, c_3 - 1], \ldots, [c_{k - 1} + 1, c_k - 1]$$$ are independent of each other. Therefore, we now only need to solve the problem where $$$a'_1 \ne -1$$$, $$$a'_n \ne -1$$$, and $$$a'_2 = a'3 = \cdots = a'{n - 1} = -1$$$.
It's clear that if $$$a_i$$$ is determined, then $$$a_{i + 1}$$$ can only be one of $$$\left\lfloor\frac{a_i}{2}\right\rfloor$$$, $$$2a_i$$$, or $$$2a_i + 1$$$.
We observe that the transition $$$a_i \to a_{i + 1}$$$ is essentially moving along an edge in a complete binary tree. Therefore, the problem is reduced to finding a path in a complete binary tree with a given start point $$$a'_1$$$, end point $$$a'_n$$$, and passing through $$$n$$$ nodes. For example, $$$a' = [3, -1, -1, -1, 9]$$$ is equivalent to finding a path from $$$3$$$ to $$$9$$$ in the complete binary tree that passes through $$$5$$$ nodes:
First, consider finding the shortest path from $$$a'_1$$$ to $$$a'_n$$$ in the complete binary tree (which can be found by computing the LCA of $$$a'_1$$$ and $$$a'_n$$$; the shortest path is $$$a'_1 \to \text{LCA}(a'_1, a'_n) \to a'_n$$$). Let the number of nodes in this shortest path be $$$l$$$. There is no solution if and only if $$$l > n$$$ or if the parities of $$$l$$$ and $$$n$$$ are different. Otherwise, we first fill $$$a'_1, a'_2, \ldots, a'_l$$$ with the nodes from the shortest path, and then alternate between $$$a'_n$$$ and $$$2a'_n$$$ to fill the remaining positions.
Time complexity: $$$O(n)$$$ or $$$O(n \log V)$$$ per test case.