A student of z-school found a kind of sorting called z-sort. The array a with n elements are z-sorted if two conditions hold:

  1. ai ≥ ai - 1 for all even i, 
  2. ai ≤ ai - 1 for all odd i > 1. 



For example the arrays [1,2,1,2] and [1,1,1,1] are z-sorted while the array [1,2,3,4] isn’t z-sorted.

Can you make the array z-sorted?

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of elements in the array a.

The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of the array a.

Output

If it's possible to make the array a z-sorted print n space separated integers ai — the elements after z-sort. Otherwise print the only word "Impossible".

Examples

Input

4
1 2 2 1


Output

1 2 1 2


Input

5
1 3 2 2 5


Output

1 5 2 3 2
#include <bits/stdc++.h>
using namespace std;
const int MAXN = int(1e3) + 20;
int n;
int zs[MAXN];
vector<int> val;
bool cmp(int a, int b) { return a > b; }
class Solution {
 public:
  void read(istream& in) {
    in >> n;
    for (int i = 0, lets_stop_here = (int)(n); i < lets_stop_here; i++) {
      int v;
      in >> v;
      val.push_back(v);
    }
  }
  void solve(istream& in, ostream& out) {
    fill(zs, zs + MAXN, 0);
    val.clear();
    read(in);
    sort(val.begin(), val.end(), cmp);
    int j = n == 1 ? 0 : 1;
    for (int i = 0, lets_stop_here = (int)(val.size()); i < lets_stop_here;
         i++) {
      int v = val[i];
      zs[j] = v;
      j = (j + 2) % n;
      if (j == 1) {
        j = 0;
      }
    }
    out << zs[0];
    for (int i = 1, lets_stop_here = (int)(n - 1); i <= lets_stop_here; i++) {
      out << " " << zs[i];
    }
    out << ("\n");
  }
};
void solve(istream& in, ostream& out) {
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  istream& in = cin;
  ostream& out = cout;
  solve(in, out);
  return 0;
}
