407714: GYM102881 C Sort?

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Sort?time limit per test1 secondmemory limit per test256 megabytesinputsorting.inoutputstandard output

Hamza has created the following sorting algorithm:

To sort an array, he calls sort(1).

He doesn't know how the array ends up after running the algorithm (sorted?), so he's asking for your help.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the length of the array.

The second line contains $$$n$$$ space-separated integers denoting the array $$$a$$$ $$$(0 \leq a_i \leq 10^9)$$$.

Output

Print the final array after running the algorithm on it.

ExamplesInput
3
1 2 3
Output
1 3 2 
Input
5
3 3 4 2 3
Output
3 3 2 3 4 
Note

For simplicity, in this portion of the problem, we'll consider the least significant $$$3$$$ bits.

The $$$and$$$ between two integers $$$x$$$ and $$$y$$$ is the bitwise anding between the two numbers:

$$$1$$$ $$$and$$$ $$$0$$$ $$$=$$$ $$$0$$$ $$$and$$$ $$$1$$$ $$$=$$$ $$$0$$$ $$$and$$$ $$$0$$$ $$$=$$$ $$$0$$$

$$$1$$$ $$$and$$$ $$$1$$$ $$$=$$$ $$$1$$$

For example:

$$$7_{10}$$$ $$$and$$$ $$$5_{10}$$$ $$$=$$$ $$$5_{10}$$$

$$$7_{10}$$$ $$$=$$$ $$${111}_2$$$, $$$5_{10}$$$ $$$=$$$ $$${101}_2$$$

$$${111}_2$$$ $$$and$$$ $$${101}_2$$$ $$$=$$$ $$${101}_2$$$ = $$$5_{10}$$$

The not of an integer $$$x$$$ is taking the complement of the integer (flipping it bits):

$$$not$$$ $$$0$$$ $$$=$$$ $$$1$$$

$$$not$$$ $$$1$$$ $$$=$$$ $$$0$$$

For example:

$$$not$$$ $$$5_{10}$$$ $$$=$$$ $$$2_{10}$$$

Explanation:

$$$5_{10}$$$ $$$=$$$ $$${101}_2$$$

$$$not$$$ $$${101}_2$$$ = $$${010}_2$$$ = $$$2_{10}$$$

Source/Category

加入题单

上一题 下一题 算法标签: