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 = 'from heapq import *\nimport sys\n\nsys.setrecursionlimit(10 ** 6)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep="\\n")\ndef MI(): return map(int, sys.stdin.readline().split())\ndef LI(): return list(map(int, sys.stdin.readline().split()))\ndef LLI(rows_number): return [LI() for _ in range(rows_number)]\n\n# lから1つおきにみたときの最小値を求める特別製\nclass SparseTable:\n    def __init__(self, aa):\n        inf = 10 ** 16\n        w = len(aa)\n        h = w.bit_length()\n        table = [aa] * 2 + [[inf] * w for _ in range(h - 2)]\n        tablei1 = table[0]\n        for i in range(2, h):\n            tablei = table[i]\n            shift = 1 << (i - 1)\n            for j in range(w):\n                rj = j + shift\n                if rj >= w: break\n                tablei[j] = min(tablei1[j], tablei1[rj])\n            tablei1 = tablei\n        self.table = table\n\n    # [l,r)の最小値\n    def min(self, l, r):\n        if (r - l) % 2: r += 1\n        i = (r - l).bit_length() - 1\n        tablei = self.table[i]\n        Lmin = tablei[l]\n        Rmin = tablei[r - (1 << i)]\n        if Lmin < Rmin: Rmin = Lmin\n        return Rmin\n\ndef main():\n    n = int(input())\n    pp = LI()\n    st = SparseTable(pp)\n    ptoi = [0] + [i for i, p in sorted(enumerate(pp), key=lambda x: x[1])]\n    # 区間偶数番目の最小値と[l,r)をヒープに\n    hp = []\n    heappush(hp, [st.min(0, n), 0, n])\n    ans = []\n    for _ in range(n // 2):\n        x, l, r = heappop(hp)\n        if l + 2 == r:\n            ans += [pp[l], pp[l + 1]]\n            continue\n        xi = ptoi[x]\n        y = st.min(xi + 1, r)\n        yi = ptoi[y]\n        if xi > l:\n            heappush(hp, [st.min(l, xi), l, xi])\n        if xi + 1 < yi:\n            heappush(hp, [st.min(xi + 1, yi), xi + 1, yi])\n        if yi < r - 1:\n            heappush(hp, [st.min(yi + 1, r), yi + 1, r])\n        ans += [x, y]\n    print(*ans)\n\nmain()\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17909