31595번 - Bit Counting Sequence 다국어

For a non-negative integer $x$, let $p(x)$ be the number of ones in the binary representation of $x$. For example, $p(26) = 3$ because $26 = (11010)_2$.

You are given a sequence of $n$ integers $(a_1, a_2, \dots , a_n)$. Your task is to determine whether there exists a non-negative integer $x$ such that $(p(x), p(x + 1), \dots , p(x + n - 1))$ is equal to $(a_1, a_2, \dots , a_n)$. Furthermore, if it exists, compute the smallest $x$ satisfying the condition.

The first line of input contains one integer $t$ ($1 ≤ t ≤ 1000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.

The first line contains one integer $n$ ($1 ≤ n ≤ 500\, 000$). The second line contains $n$ integers $a_1, a_2, \dots , a_n$ ($0 ≤ a_i ≤ 60$ for all $i$).

The sum of $n$ across all test cases in one input file does not exceed $500\, 000$.

For each test case, output the smallest non-negative integer $x$ satisfying the condition above. If there is no such $x$, output -1 instead.