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

public class Main{
  static int n;
  static int[] p;

  static final int MAX = 200000;
  static final boolean DEBUG = false;

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    p = new int[n];
    for(int i = 0; i < n; i++){
      p[i] = sc.nextInt();
    }

    int[] pos = new int[MAX + 1];
    for(int i = 0; i < n; i++){
      pos[p[i]] = i;
    }

    RangeMinimumTree re = new RangeMinimumTree(n);
    RangeMinimumTree ro = new RangeMinimumTree(n);
    for(int i = 0; i < n; i++){
      if(i % 2 == 0){
        re.update(i, p[i]);
      }
      else{
        ro.update(i, p[i]);
      }
    }

    int[] ans = new int[n];
    int sp = 0;

    PriorityQueue< Interval > pq = new PriorityQueue< >();
    pq.offer(new Interval(0, n, re.get(0, n)));

    while(sp < n){
      Interval interval = pq.poll();

      int p0 = interval.val;
      int p1 = ((pos[p0]  + 1) % 2 == 1 ?
        ro.get(pos[p0] + 1, interval.b) : re.get(pos[p0] + 1, interval.b));

      if(DEBUG){
        System.out.println("p0 = " + p0);
        System.out.println("p1 = " + p1);
        System.out.println("pos[p0] = " + pos[p0]);
        System.out.println("pos[p1] = " + pos[p1]);
      }

      ans[sp++] = p0;
      ans[sp++] = p1;

      Interval i1 = new Interval(interval.a, pos[p0],
          (interval.a % 2 == 0 ?
           re.get(interval.a, pos[p0]) : ro.get(interval.a, pos[p0])));

      Interval i2 = new Interval(pos[p0] + 1, pos[p1],
          ((pos[p0] + 1) % 2 == 0 ?
           re.get(pos[p0] + 1, pos[p1]) : ro.get(pos[p0] + 1, pos[p1])));

      Interval i3 = new Interval(pos[p1] + 1, interval.b,
          ((pos[p1] + 1) % 2 == 0
           ? re.get(pos[p1] + 1, interval.b) : ro.get(pos[p1] + 1, interval.b)));

      pq.offer(i1);
      pq.offer(i2);
      pq.offer(i3);

      if(DEBUG){
        System.out.println(i1);
        System.out.println(i2);
        System.out.println(i3);
      }
    }

    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < n; i++){
      sb.append(ans[i] + " ");
    }

    System.out.println(sb);
  }

  static class Interval implements Comparable< Interval >{
    int a, b;
    int val;

    Interval(int a, int b, int val){
      this.a = a;
      this.b = b;
      this.val = val;
    }

    @Override
      public int compareTo(Interval i){
        return Integer.compare(val, i.val);
      }

    @Override
      public String toString(){
        return "a = " + a + ", b = " + b + ", val = " + val;
      }
  }
}

class RangeMinimumTree {
  static final int MAX = Integer.MAX_VALUE / 2;
  int n;
  int[] tree;

  RangeMinimumTree(int n){
    this.n = 1;
    while(this.n < n){
      this.n <<= 1;
    }
    this.tree = new int[this.n << 2];
    for(int i = 0; i < tree.length; i++){
      tree[i] = MAX;
    }
  }

  void update(int i, int x){
    i += n - 1;
    tree[i] = x;
    while(i > 0){
      i = (i - 1) / 2;
      tree[i] = Math.min(tree[2 * i + 1], tree[2 * i + 2]);
    }
  }

  int get(int a, int b){
    return get(a, b, 0, 0, n);
  }

  int get(int a, int b, int i, int l, int h){
    if(h <= a || b <= l){
      return MAX;
    }
    if(a <= l && h <= b){
      return tree[i];
    }
    int vl = get(a, b, 2 * i + 1, l, (l + h) / 2);
    int vr = get(a, b, 2 * i + 2, (l + h) / 2, h);
    return Math.min(vl, vr);
  }
}