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.PrintWriter;
import java.util.Scanner;

public class z_sort_B_CF {

	static void mergeSort(int[]a,int s,int e) {
		if(e>s)
		{
			// mid point
			int m = (e+s)/2;
			// sort left
			mergeSort(a,s,m);
			//sort right
			mergeSort(a,m+1,e);
			//merge
			merge(a,s,m,e);
		}
	}
	static void merge(int[]a,int s,int m,int e) {
		int n1=m-s+1,n2=e-m;
		int[] t1= new int[n1],t2=new int[n2];
		for(int i=0;i<n1;i++)
		{
			t1[i]=a[i+s];
		}
		for(int i=0;i<n2;i++)
		{
			t2[i]=a[m+1+i];
		}
		int i=0,j=0,k=s;
		while(i<n1 && j<n2)
		{
			if(t1[i]<=t2[j])
			{
				a[k++]=t1[i++];
			}
			else
			{
				a[k++]=t2[j++];
			}
		}
		while(i<n1)
		{
			a[k++]=t1[i++];
		}
		while(j<n2)
		{
			a[k++]=t2[j++];
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		if(n==0)
		{
			out.println("");
			return;
		}
		int[]a = new int[n];
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();
		}
		mergeSort(a,0,n-1);
		int[] res = new int[n];
		int k=0;
		for(int i=0;i<=((n-1)/2);i++)
		{
			res[k]=a[i];
			k+=2;
		}
		k=1;
		for(int i=n-1;i>=((n-1)/2)+1;i--)
		{
			res[k]=a[i];
			k+=2;
		}
		for(int i=0;i<n-1;i++)
		{
			out.print(res[i]+" ");
		}
		out.println(res[n-1]);
		out.flush();
		out.close();
	}

}
