Reorder List

Problem statement

A gallery displays a linked chain of photographs. To interleave the oldest and newest images, the curator wants the first image, then the last, then the second, then the second-last, continuing toward the center. Your task Reorder L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 and so on. Build a singly linked list from the input values and perform the operation on its nodes. Important details Change links, not stored values. Each node must appear exactly once. Use O(n) time and O(1) extra space by finding the midpoint, reversing the second half, and merging the two halves. Odd-length lists have one final middle node. Worked example The sequence 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 5 -> 2 -> 4 -> 3. The middle photograph appears last.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

1 <= n <= 50000; 1 <= values <= 1000.

Sample input

5
1 2 3 4 5

Sample output

1 5 2 4 3