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.

-----Sample Input-----
4
3 2 4 1

-----Sample Output-----
3 1 2 4

The solution above is obtained as follows:pq(3, 2, 4, 1)()↓↓(3, 1)(2, 4)↓↓()(3, 1, 2, 4)

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '#####segfunc#####\ndef segfunc(x, y):\n    if y[0]>x[0]:\n        return x\n    else:\n        return y\n#################\n\n#####ide_ele#####\nide_ele =(float("inf"),-1)\n#################\n\nclass SegTree:\n    """\n    init(init_val, ide_ele): 配列init_valで初期化 O(N)\n    update(k, x): k番目の値をxに更新 O(logN)\n    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)\n    """\n    def __init__(self, init_val, segfunc, ide_ele):\n        """\n        init_val: 配列の初期値\n        segfunc: 区間にしたい操作\n        ide_ele: 単位元\n        n: 要素数\n        num: n以上の最小の2のべき乗\n        tree: セグメント木(1-index)\n        """\n        n = len(init_val)\n        self.segfunc = segfunc\n        self.ide_ele = ide_ele\n        self.num = 1 << (n - 1).bit_length()\n        self.tree = [ide_ele] * 2 * self.num\n        # 配列の値を葉にセット\n        for i in range(n):\n            self.tree[self.num + i] = init_val[i]\n        # 構築していく\n        for i in range(self.num - 1, 0, -1):\n            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])\n\n    def update(self, k, x):\n        """\n        k番目の値をxに更新\n        k: index(0-index)\n        x: update value\n        """\n        k += self.num\n        self.tree[k] = x\n        while k > 1:\n            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])\n            k >>= 1\n\n    def query(self, l, r):\n        """\n        [l, r)のsegfuncしたものを得る\n        l: index(0-index)\n        r: index(0-index)\n        """\n        res = self.ide_ele\n\n        l += self.num\n        r += self.num\n        while l < r:\n            if l & 1:\n                res = self.segfunc(res, self.tree[l])\n                l += 1\n            if r & 1:\n                res = self.segfunc(res, self.tree[r - 1])\n            l >>= 1\n            r >>= 1\n        return res\n\nimport heapq\n\nN=int(input())\np=list(map(int,input().split()))\nn=N//2\nop=[(p[2*i+1],2*i+1) for i in range(n)]\nep=[(p[2*i],2*i) for i in range(n)]\n\noseg=SegTree(op,segfunc,ide_ele)\neseg=SegTree(ep,segfunc,ide_ele)\n\ndef first(l,r):\n    if l>=r:\n        return (-1,-1,-1,-1)\n    if l%2==0:\n        val,index=eseg.query(l//2,r//2)\n        val2,index2=oseg.query(index//2,r//2)\n        return (val,val2,index,index2)\n    else:\n        val,index=oseg.query(l//2,r//2)\n        val2,index2=eseg.query(index//2+1,r//2+1)\n        return (val,val2,index,index2)\n\nval,val2,index,index2=first(0,N)\nque=[((val,val2),0,N)]\nheapq.heapify(que)\nans=[]\nwhile que:\n    tuple,l,r=heapq.heappop(que)\n    ans.append(tuple[0])\n    ans.append(tuple[1])\n    val,val2,index,index2=first(l,r)\n    val,val2,l1,r1=first(l,index)\n    if val!=-1:\n        heapq.heappush(que,((val,val2),l,index))\n    val,val2,l2,r2=first(index+1,index2)\n    if val!=-1:\n        heapq.heappush(que,((val,val2),index+1,index2))\n    val,val2,l3,r3=first(index2+1,r)\n    if val!=-1:\n        heapq.heappush(que,((val,val2),index2+1,r))\n\nprint(*ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17311