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.*;
import java.util.*;
public class zSort2 {
    static int c = 0 ;
    static int [] arr ;
    public static void main(String args []) throws IOException {
        Scanner sc = new Scanner(System.in);

            int l = sc.nextInt();

            arr= new int[l];
            for (int i = 0 ; i<l ; i++){
                arr[i]= sc.nextInt();
            }
            int ar [] = merge(0, l-1);
            int i = 0 , j = ar.length-1;
            while(i<j){
                System.out.print(ar[i] + " " + ar[j]+" ");
                ++i;
                --j;
            }
            if (i == j){
                System.out.print(ar[i]);
            }
        }

    static  int [] merge(int b , int e){
        if (e == b) return new int[]{arr[b]} ;
        int mid = (b+e)/2;
        int [] left = merge(b,mid);
        int [] right = merge(mid +1 , e);
        int [] result = new int[e-b+1];
        int i = 0 , j = 0 , idx = 0 ;
        while(i<left.length&&j<right.length){
            if (left[i]<=right[j])
                result[idx++]=left[i++];
            else{
                result[idx++] = right[j++];
                c+= left.length-i;
            }
        }
        while(i< left.length)
            result[idx++]=left[i++];
        while (j<right.length){
            result[idx++]=right[j++];
        }
        return result ;
    }

    static class Scanner
    {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {br = new BufferedReader(new InputStreamReader(system));}
        public Scanner(String file) throws Exception {br = new BufferedReader(new FileReader(file));}
        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        public String nextLine()throws IOException{return br.readLine();}
        public int nextInt() throws IOException {return Integer.parseInt(next());}
        public double nextDouble() throws IOException {return Double.parseDouble(next());}
        public char nextChar()throws IOException{return next().charAt(0);}
        public Long nextLong()throws IOException{return Long.parseLong(next());}
        public boolean ready() throws IOException{return br.ready();}
        public void waitForInput() throws InterruptedException {Thread.sleep(3000);}
    }
}
