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;
long long int gcd(long long int a, long long int b) {
  return (b == 0 ? a : gcd(b, a % b));
}
long long int lcm(int a, int b) { return (a * (b / gcd(a, b))); }
long long int max(long long int a, long long int b, long long int c) {
  return max(a, max(b, c));
}
long long int power(long long int x, long long int y) {
  long long int ans = 1;
  while (y > 0) {
    if (y & 1) ans = (ans * x) % 1000000007;
    x = (x * x) % 1000000007;
    y /= 2;
  }
  return ans;
}
int main() {
  long long int t, n;
  cin >> n;
  t = ceil(n / 2);
  long long int a[n + 1], b[n + 1], c[n + 1];
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  memset(c, 0, sizeof(c));
  int k = 0, l = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i];
    c[i] = a[i];
  }
  sort(b + 1, b + n + 1);
  sort(c + 1, c + n + 1, greater<int>());
  k = 1;
  l = 1;
  for (int i = 1; i <= n; i++) {
    if (i & 1) {
      a[i] = b[k];
      k++;
    } else {
      a[i] = c[l];
      l++;
    }
  }
  int flag = 0;
  for (int i = 2; i <= n; i++) {
    if (i & 1) {
      if (a[i] > a[i - 1]) {
        flag = 1;
        break;
      }
    } else {
      if (a[i] < a[i - 1]) {
        flag = 1;
        break;
      }
    }
  }
  if (flag == 1)
    cout << "Impossible" << endl;
  else {
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << endl;
  }
}
