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.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static class SegmentTree {
        int n;
        long []data;
        long DEFAULT_VALUE = Long.MAX_VALUE;

        // when father is k, left son is 2 * k + 1, right son is 2 * k + 2.

        public SegmentTree(long[] num) {
            n = 1;
            while (n < num.length) {
                n *= 2;
            }
            data = new long[2 * n];
            for (int i = 0; i < num.length; ++i) {
                update(i, num[i]);
            }

        }

        // update original array[index] to newValue
        void update(int index, long newValue) {
            index += n - 1;
            data[index] = newValue;
            while (index > 0) {
                index = (index - 1) / 2;
                data[index] = Math.min(data[index * 2 + 1], data[index * 2 + 2]);
            }
        }

        // query min value in [a, b)
        // k is the index of tree node in data
        // [l, r) is the interval that represent by current node k.
        // to get min value in [a, b), call from outside: query(a, b, 0, 0, n);
        long query(int a, int b, int k, int l, int r) {
            // current node k 's interval is outside of query interval[a, b)
            if (r <= a || l >= b) {
                return DEFAULT_VALUE;
            }
            // current node k is subset of query interval[a, b)
            if (a <= l && r <= b) {
                return data[k];
            }
            // current node k is contains part of query interval [a, b)
            long leftSon = query(a, b, 2 * k + 1, l, (l + r) / 2);
            long rightSon = query(a, b, 2 * k + 2, (l + r) / 2, r);
            return Math.min(leftSon, rightSon);
        }


    }
    public static class Interval implements Comparable<Interval> {
        int l;
        int r;
        long value;
        public Interval(int l, int r, long value) {
            this.l = l;
            this.r = r;
            this.value = value;
        }

        @Override
        public int compareTo(Interval o) {
            if (this.value == o.value) {
                return 0;
            } else if (this.value > o.value) {
                return 1;
            } else {
                return -1;
            }
        }
    }
    public static void main(String [] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long [] num = new long[n];
        long [] oddNum = new long[n];
        long [] evenNum = new long[n];
        Map<Long, Integer> valueToIndex = new HashMap<>();

        for (int i = 0; i < n; ++i) {
            num[i] = scanner.nextLong();
            oddNum[i] = Long.MAX_VALUE;
            evenNum[i] = Long.MAX_VALUE;
            valueToIndex.put(num[i], i);
        }
        for (int i = 1; i < n; i += 2) {
            oddNum[i] = num[i];
        }
        for (int i = 0; i < n; i += 2) {
            evenNum[i] = num[i];
        }

        final SegmentTree oddTree = new SegmentTree(oddNum);
        final SegmentTree evenTree = new SegmentTree(evenNum);
        PriorityQueue<Interval> intervals = new PriorityQueue<>();
        long first = evenTree.query(0, n, 0, 0, evenTree.n);
        intervals.add(new Interval(0, n, first));
        long [] ans = new long[n];
        for (int i = 0; i < n; ++i) {
            Interval currentInterval = intervals.poll();
            ans[i] = currentInterval.value;
            int left = currentInterval.l;
            int right = currentInterval.r;
            int pickedLeftIndex = valueToIndex.get(currentInterval.value);

            long pickedRightValue;
            int pickedRightIndex;
            if (pickedLeftIndex % 2 == 1) {
               pickedRightValue = evenTree.query(pickedLeftIndex + 1, right, 0, 0, evenTree.n);
            } else {
                pickedRightValue = oddTree.query(pickedLeftIndex + 1, right, 0, 0, oddTree.n);
            }
            pickedRightIndex = valueToIndex.get(pickedRightValue);
            ans[++i] = pickedRightValue;
            // the interval cut into:
            // [left, pickedLeftIndex)
            // [pickedLeftIndex + 1, pickedRightIndex)
            // [pickedRightIndex + 1, right)

            long leftValue1 = getLeftValueForCurrentInterval(left, pickedLeftIndex, evenTree, oddTree);
            intervals.add(new Interval(left, pickedLeftIndex, leftValue1));

            long leftValue2 = getLeftValueForCurrentInterval(pickedLeftIndex + 1, pickedRightIndex, evenTree, oddTree);
            intervals.add(new Interval(pickedLeftIndex + 1, pickedRightIndex, leftValue2));

            long leftValue3 = getLeftValueForCurrentInterval(pickedRightIndex + 1, right, evenTree, oddTree);
            intervals.add(new Interval(pickedRightIndex + 1, right, leftValue3));

        }
        for (int i = 0; i < n; ++i) {
            System.out.print(ans[i] + " ");
        }

    }

    public static long getLeftValueForCurrentInterval(int l, int r, SegmentTree evenTree, SegmentTree oddTree) {
        SegmentTree segmentTree;
        if (l % 2 == 0) {
            segmentTree = evenTree;
        } else {
            segmentTree = oddTree;
        }
        return segmentTree.query(l, r, 0, 0, evenTree.n);
    }
}