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 = 'import sys\ninput = sys.stdin.readline\n\n# O(NlogN)構築、クエリO(1)のRMQ\n# 変更はできない\nclass SparseTable():\n    def __init__(self, N, A):\n        self.N = N\n        self.logN = N.bit_length()\n        self.A = A\n        self.table = [[i for i in range(N)]]\n        for k in range(self.logN):\n            tab = []\n            for i in range(self.N-(1<<(k+1))+1):\n                ind1 = self.table[-1][i]\n                ind2 = self.table[-1][i+(1<<k)]\n                if self.A[ind1] <= self.A[ind2]:\n                    tab.append(ind1)\n                else:\n                    tab.append(ind2)\n            self.table.append(tab)\n    \n    # [l, r)のminの(val, key)\n    def query_min(self, l, r):\n        k = (r-l).bit_length()-1\n        indl = self.table[k][l]\n        indr = self.table[k][r-(1<<k)]\n        if self.A[indl] <= self.A[indr]:\n            return self.A[indl], indl\n        return self.A[indr], indr\n\nimport heapq as hp\nN = int(input())\nA = list(map(int, input().split()))\n\ndef main():\n    SP1 = SparseTable((N+1)//2, A[::2])\n    SP2 = SparseTable(N//2, A[1::2])\n\n    ans = []\n    q = []\n    v, k = SP1.query_min(0, N//2)\n    dic = {}\n    dic[v] = (k, 0, N//2, True)\n    hp.heappush(q, v)\n    for _ in range(N//2):\n        valuea = hp.heappop(q)\n        ka, l, r, is1 = dic[valuea]\n        ans.append(str(valuea))\n        if is1:\n            valueb, kb = SP2.query_min(ka, r)\n            if ka < kb:\n                m2, nk2 = SP2.query_min(ka, kb)\n                hp.heappush(q, m2)\n                dic[m2] = (nk2, ka, kb+1, False)\n            if l < ka:\n                m1, nk1 = SP1.query_min(l, ka)\n                hp.heappush(q, m1)\n                dic[m1] = (nk1, l, ka, True)\n            if kb+1 < r:\n                m3, nk3 = SP1.query_min(kb+1, r)\n                hp.heappush(q, m3)\n                dic[m3] = (nk3, kb+1, r, True)\n        else:\n            valueb, kb = SP1.query_min(ka+1, r)\n            if ka+1 < kb:\n                m1, nk1 = SP1.query_min(ka+1, kb)\n                hp.heappush(q, m1)\n                dic[m1] = (nk1, ka+1, kb, True)\n            if l < ka:\n                m2, nk2 = SP2.query_min(l, ka)\n                hp.heappush(q, m2)\n                dic[m2] = (nk2, l, ka+1, False)\n            if kb < r-1:\n                m3, nk3 = SP2.query_min(kb, r-1)\n                hp.heappush(q, m3)\n                dic[m3] = (nk3, kb, r, False)\n\n        ans.append(str(valueb))\n\n    print(" ".join(ans))\n\n\ndef __starting_point():\n    main()\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 16031