146. Split by Position

Challenge1000 ms256 MBSolved by 0%

Rearrange the list so that all nodes at EVEN positions come first, in their original order, followed by all nodes at ODD positions, also in their original order. Positions are 0-based.

So 1 2 3 4 5 becomes 1 3 5 2 4.

Relink the existing nodes rather than building a new list. Print Empty for an empty list.

Constraints - `0 ≤ n ≤ 100000` - `-1000000 ≤ value ≤ 1000000`

Input

The first line contains an integer n, the number of nodes. The second line contains n space-separated integers — the node values from head to tail. The starter code builds the list for you; work on the nodes, not the array.

Output

Print the resulting list from head to tail on ONE line, separated by single spaces, or Empty if no nodes remain.

Input5 1 2 3 4 5

Output1 3 5 2 4

Noteis the worked example from the statement

Input4 1 2 3 4

Output1 3 2 4

Notehas an even length, so both groups end cleanly

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution