Problem Description

The binary representation of a non-negative integer can be viewed as a $01$ string, with the left side being the most significant bit and the right side being the least significant bit. If it has at most $k$ consecutive bits equal to $1$, then the number’s “consecutive order” is defined as $k$. Given $n$ non-negative integers, sort them in increasing order of their “consecutive order”. If two numbers have the same consecutive order, output the one with the smaller value first.

For example, the binary representations of $7$, $12$, and $27$ are ${\left(111\right)}_2$, ${\left(1100\right)}_2$, and ${\left(11011\right)}_2$, respectively. Their consecutive orders are $3$, $2$, and $2$. Since $12$ and $27$ have the same consecutive order but $12 < 27$, the output should be, in order, $12$, $27$, $7$.

Input Format

$$\begin{aligned} &n \\ &a_1 \; a_2 \; a_3 \; \cdots \; a_n \end{aligned}$$

• $n$ is the number of integers to be sorted.
• $a_i$ is the $i$-th integer to be sorted.

Output Format

$$\begin{aligned} &s_1 \; s_2 \; s_3 \; \cdots \; s_n \end{aligned}$$

• $s_i$ is the $i$-th integer after sorting according to the requirements.

3
7 12 27

12 27 7

5
1 2 3 4 5

1 2 4 5 3

Hint

Constraints

• $1 \le n \le 2 \times {10}^5$.
• $0 \le a_i < 2^{30}$.
• All input numbers are integers.

Scoring

This problem has four subtasks with the following constraints. Each subtask may contain one or more testdata files. You will get the score for a subtask only if you answer all testdata files in that subtask correctly.

Subtask	Score	Additional Input Constraints
1	22	$n \le 2,\ a_i < 16$。
2		$n \le 2\,000,\ a_i < 2^{16}$。
3	26	$a_i < 2^{16}$。
4	30	No additional constraints.

Translated by ChatGPT 5