Problem: Let N be a positive even number.

We have a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Snuke is constructing another permutation of (1, 2, ..., N), q, following the procedure below.

First, let q be an empty sequence. Then, perform the following operation until p becomes empty:

* Select two adjacent elements in p, and call them x and y in order. Remove x and y from p (reducing the length of p by 2), and insert x and y, preserving the original order, at the beginning of q.



When p becomes empty, q will be a permutation of (1, 2, ..., N).

Find the lexicographically smallest permutation that can be obtained as q.

Constraints

* N is an even number.
* 2 ≤ N ≤ 2 × 10^5
* p is a permutation of (1, 2, ..., N).

Input

Input is given from Standard Input in the following format:


N
p_1 p_2 ... p_N


Output

Print the lexicographically smallest permutation, with spaces in between.

Examples

Input

4
3 2 4 1


Output

3 1 2 4


Input

2
1 2


Output

1 2


Input

8
4 6 3 2 8 5 7 1


Output

3 1 2 7 4 6 8 5

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

import static java.lang.System.in;
class Main {
    static int[] idx;
    static int[] A;
    static ST even;
    static ST odd;
    static ST all;
    public static void main(String[] args) throws IOException{
        //Scanner sc = new Scanner(System.in);
        //int n = sc.nextInt();
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        String temp;
        String[] buf;
        temp = reader.readLine();
        int n = Integer.parseInt(temp);
        temp = reader.readLine();
        buf = temp.split(" ");

        A = new int[n];
        idx = new int[n+1];
        for(int i=0;i<n;i++){
            A[i] = Integer.parseInt(buf[i]);
            idx[A[i]] = i;
        }
        even = new ST(n/2);
        odd = new ST(n/2);
        all = new ST(n);

        for(int i=0;i<n;i+=2) even.update(i/2,A[i]);
        for(int i=1;i<n;i+=2) odd.update(i/2,A[i]);
        for(int i=0;i<n;i++) all.update(i,A[i]);
        myComparator mc = new myComparator();
        PriorityQueue<int[]> pq = new PriorityQueue<>(10,mc);
        pq.add(new int[]{0,n});
        ArrayList<Integer> res = new ArrayList<>();
        while(res.size()<n){
            int[] cur = pq.poll();
            int left = cur[0];
            int right = cur[1];
            int now,next;
            if(left%2==0){
                now = even.find(left/2,right/2);
                next = odd.find((idx[now]+1)/2,(right+1)/2);
            }else{
                now = odd.find(left/2,right/2);
                next = even.find((idx[now]+1)/2,(right+1)/2);
            }
            res.add(now);
            res.add(next);
            if(left<idx[now]) pq.add(new int[]{left,idx[now]});
            if(idx[now]<idx[next]-1) pq.add(new int[]{idx[now]+1,idx[next]});
            if(idx[next]<right-1) pq.add(new int[]{idx[next]+1,right});
        }
        for(int i=0;i<res.size();i++){
            System.out.print(Integer.toString(res.get(i))+" ");
        }
    }

    static class ST{
        int n=1;
        int[] dat;
        public ST(int n_){
            while(n<n_) n*=2;
            dat = new int[2*n-1];
            for(int i=0;i<2*n-1;i++) dat[i] = Integer.MAX_VALUE/2;
        }
        public void update(int idx, int val){
            idx += n-1;
            dat[idx] = val;
            while(idx>0){
                idx = (idx-1)/2;
                dat[idx] = Math.min(dat[idx*2+1],dat[idx*2+2]);
            }
        }
        public int find(int a, int b){
            return query(a,b,0,0,n);
        }
        private int query(int a, int b, int k, int left, int right){
            if(b<=left||right<=a) return Integer.MAX_VALUE;
            if(a<=left&&right<=b) return dat[k];
            int v1 = query(a,b,2*k+1,left,(left+right)/2);
            int v2 = query(a,b,2*k+2,(left+right)/2,right);
            return Math.min(v1,v2);
        }
    }
    static class myComparator implements Comparator<int[]>{
        public int compare(int[] o1, int[] o2){
            int[][] dic = new int[][]{o1,o2};
            int[] res = new int[2];
            for(int i=0;i<2;i++){
                int[] cur = dic[i];
                int left = cur[0];
                int right = cur[1];
                int p = left%2==0?even.find(left/2,right/2):odd.find(left/2,right/2);
                res[i]=p;
            }
            return res[0]-res[1];
        }
    }
}