182. Interleave the Two Halves

Core1000 ms256 MBSolved by 0%

Split the queue down the middle and interleave the halves, taking one value from the front half and then one from the back half, until both are used up.

So 1 2 3 4 becomes 1 3 2 4 — first half 1 2, second half 3 4, alternated.

Print Invalid if the queue has an odd number of values, since it cannot be split evenly.

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

Input

The first line contains an integer n. The second line contains n space-separated integers, in queue order from front to back.

Output

Print the interleaved queue from front to back — n integers on one line, separated by single spaces. Print Invalid if n is odd.

Input4 1 2 3 4

Output1 3 2 4

Noteis the worked example from the statement

Input6 11 12 13 14 15 16

Output11 14 12 15 13 16

Noteinterleaves halves of three each

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution