## Problem S2: High Tide, Low Tide

Joe Coder is camping near the Bay of Fundy between Nova Scotia and New Brunswick. When he arrived at the bay, he was told that the difference in height between high tide and low tide at the Bay of Fundy was the largest tidal difference in the world. Ever the skeptic, Joe decided to verify this. He chose a reference point and, after learning from the radio when the tides were highest and lowest, he went with a boat to his reference point and measured the depth of the water. Unfortunately, on the last day of his trip, a strong wind scattered his measurements.

Joe has recovered all of his measurements, but they may not be in their original order. Luckily, he remembers some things about his measurements:

• He started measuring water levels at a low tide, his second measurement was of the water level at high tide, and after that the measurements continued to alternate between low and high tides.
• All high tide measurements were higher than all low tide measurements.
• Joe noticed that as time passed, the high tides only became higher and the low tides only became lower.

Given Joe's measurements in no particular order, you must reconstruct the correct order in which the measurements were taken.

### Input Format

The first line contains the integer N (1 ≤ N ≤ 100). The next line contains N distinct space-separated integers, where each integer is at most 1 000 000.

### Output Format

Output the N integers in the unique order that Joe originally took the measurements.

### Sample Input

```8
10 50 40 7 3 110 90 2
```

### Sample Output

```10 40 7 50 3 90 2 110
```

### Explanation

The low tide measurements (in order) were 10, 7, 3, and 2. The high tide measurements (in order) were 40, 50, 90, and 110.

Point Value: 7
Time Limit: 1.00s
Memory Limit: 16M
Added: Aug 08, 2017

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (0/1)
I'm the sample output right but none of the test cases.

• (2/0)
IndexOfBoundsException, what if n is odd?

• (0/0)
I'm getting 14/15 for this question, but on one of the cases its giving me a runtime error (status = 1). I've looked through my code and I'm not sure what the error is, could someone give me some help?

• (1/0)
IndexOutOfBoundsException

• (0/0)
Thanks alot! Got it now.