Problem D: No average

## Problem D: No average

Time Limit: 1 Sec  Memory Limit: 128 MB  Special Judge
Submit: 668  Solved: 295
[Submit][Status][Web Board]

## Description

Given a sequence $$\{a\}$$ with  $$n$$ different numbers (n is even). Please permutate this sequence to form a circle, so that each element on this circle is not equal to the average of two neighbors.

More formally, find an permutation $$\{b\}$$ of sequence $$\{a\}$$, such that:

• $$\forall i \in \{2, 3, ..., n-1\}, b_i \neq \frac{b_{i-1}~+ b_{i+1}}{2}$$
• $$b_1 \neq \frac{b_2 + b_n}{2}$$
• $$b_n \neq \frac{b_{n-1} ~+~ b_1}2$$

There may be more than one answer, you just need to print one of them.

We guarantee that there is at least one solution for each test case.

## Input

The first line will be a integers $$n$$ as we mentioned before.

The second line will be $$n$$ integers in sequence, $$a_1, a_2, ..., a_n$$

For all test cases, $$n$$ is even and $$3 <= n<= 10^6, 0\leq a_i\leq 10^9$$

## Output

The only line will be $$n$$ integers, $$b_1, b_2, ..., b_n$$

## Sample Input

6
3 2 1 4 5 6

## Sample Output

1 2 4 3 5 6

## HINT

You may need this. Java FastIO template: https://paste.ubuntu.com/p/6ybMcVXvz5/

[Submit][Status]