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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class ZSort {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		int n = Integer.parseInt(br.readLine());
		long[] vals = new long[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<vals.length;i++) {
			vals[i] = Long.parseLong(st.nextToken());
		}
		mergeSort(vals, 0, n-1);
		ArrayList<Long> fin = new ArrayList<>();
		int start = 0, end=vals.length-1;
		while(start<=end) {
			if(start<end) {
				fin.add(vals[start++]);
				fin.add(vals[end--]);
			}
			else
				fin.add(vals[start++]);
		}
		boolean valid = true;
		for(int i=1;i<fin.size();i+=2) {
			if(fin.get(i)<fin.get(i-1)) {
				valid = false;
				break;
			}
		}
		if(valid) {
			for(int i=2;i<fin.size();i+=2) {
				if(fin.get(i)>fin.get(i-1)) {
					valid = false;
					break;
				}
			}
		}
		if(!valid)
			pw.println("Impossible");
		else {
			for(long x : fin)
				pw.print(x+" ");
		}
		pw.close();
	}
	
	public static void mergeSort(long[] a,int b,int e) {
		if(b<e) {
			int mid = (b+e)/2;
			mergeSort(a, b, mid);
			mergeSort(a, mid+1, e);
			merge(a,b,mid,e);			
		}
	}
	
	public static void merge(long[] a,int b,int mid,int e) {
		int s1 = mid-b+1;
		int s2 = e-mid;
		long[] left = new long[s1+1];
		long[] right = new long[s2+1];
		left[s1] = Long.MAX_VALUE;
		right[s2] = Long.MAX_VALUE;
		for(int i=0;i<s1;i++)
			left[i] = a[b+i];
		for(int i=0;i<s2;i++)
			right[i] = a[mid+i+1];
		for(int k=b,i=0,j=0;k<=e;k++) {
			if(left[i]<=right[j])
				a[k] = left[i++];
			else
				a[k] = right[j++];
		}
	}

}
