A toll lane's waiting queue is a singly linked list of vehicle IDs. Using 1-based positions along the queue (the first vehicle is at position 1, the second at position 2, and so on), regroup the queue so that all vehicles originally at ODD positions come first, in their original relative order, followed by all vehicles originally at EVEN positions, also in their original relative order. Print the resulting IDs.
Input format
Line 1: an integer n — the number of vehicles.
Line 2: n space-separated integers — the vehicle IDs, front to back.
Output format
n space-separated integers: the odd-position IDs (in order) followed by the even-position IDs (in order).
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ vehicle ID ≤ 1000000000