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]


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.


 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\)


The only line will be \(n\) integers, \(b_1, b_2, ..., b_n\)

Sample Input

3 2 1 4 5 6

Sample Output

1 2 4 3 5 6


You may need this. Java FastIO template: