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


public class zSort {
	static void mergeSort(int arr[], int array_size)
	 {
	     int temp[] = new int[array_size];
	      _mergeSort(arr, temp, 0, array_size - 1);
	 }
	   
	 static void _mergeSort(int arr[], int temp[], int left, int right)
	 {
	   int mid, inv_count = 0;
	   if (right > left)
	   {
	     mid = (right + left)/2;
	     _mergeSort(arr, temp, left, mid);
	      _mergeSort(arr, temp, mid+1, right);
	      merge(arr, temp, left, mid+1, right);
	   }
	 }
	   
	 
	 static void merge(int arr[], int temp[], int left, int mid, int right)
	 {
	   int i, j, k;
	   i = left; 
	   j = mid;  
	   k = left;
	   while ((i <= mid - 1) && (j <= right))
	   {
	     if (arr[i] <= arr[j])
	     {
	       temp[k++] = arr[i++];
	     }
	     else
	     {
	       temp[k++] = arr[j++];
	     }
	   }	   
	   while (i <= mid - 1)
	     temp[k++] = arr[i++];
	   while (j <= right)
	     temp[k++] = arr[j++];
	   for (i=left; i <= right; i++)
	     arr[i] = temp[i];
	 }

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();
		int [] in = new int[size];
		for(int i=0;i<size;i++){
			in[i]= sc.nextInt();
		}
		mergeSort(in, size);
		int [] zSort = new int [size];
		boolean impossible = false;
		int mid ;
		if(size%2==0)
			mid=size/2;
		else
			mid = size/2+1;
		int newSize = mid;
		int pointer = 0;
		for(int i=0;i<newSize;i++){
			zSort[pointer]=in[i];
			if(mid<size){
				zSort[pointer+1] = in[mid++];
			pointer+=2;
			}
			else
				pointer+=1;
		}
		StringBuilder out = new StringBuilder();
		for(int i = 0;i <size;i++){
			out.append(zSort[i]);
			if(i<size-1)
				out.append(" ");
		}
		System.out.println(out);
		
	}
	  static class Scanner {
	        BufferedReader br;
	        StringTokenizer st;
	 
	        Scanner(InputStream s) {
	            br = new BufferedReader(new InputStreamReader(s));
	        }
	 
	        Scanner(FileReader s) {
	            br = new BufferedReader(s);
	        }
	 
	        String next() throws IOException {
	            while (st == null || !st.hasMoreTokens())
	                st = new StringTokenizer(br.readLine());
	            return st.nextToken();
	        }
	 
	        int nextInt() throws IOException {
	            return Integer.parseInt(next());
	        }
	 
	        long nextLong() throws IOException {
	            return Long.parseLong(next());
	        }
	    }

}
