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 = 'def main():\n    n = int(input())\n    p = list([int(x)-1 for x in input().split()])\n\n    pos = [j for i, j in sorted([(j, i) for i, j in enumerate(p)])]\n    basesize = n >> 1\n    num = 1\n    while num < basesize:\n        num *= 2\n    num -= 1\n\n    tree_even = [100001]*(num*2+1)\n    tree_odd = [100001]*(num*2+1)\n\n    for i in range(num, num+basesize):\n        tree_even[i] = p[(i-num)*2]\n    for i in range(num-1, -1, -1):\n        tree_even[i] = min(tree_even[2*i+1:2*i+3])\n    for i in range(num, num+basesize):\n        tree_odd[i] = p[(i-num)*2+1]\n    for i in range(num-1, -1, -1):\n        tree_odd[i] = min(tree_odd[2*i+1:2*i+3])\n\n    g = dict()\n    d = dict()\n    q = [n-1]\n    qap, qp = q.append, q.pop\n    while q:\n        t = qp()\n        m, M = t//n, t % n\n        if m+1 == M:\n            d[t] = p[m]*n+p[M]\n            continue\n        g[t] = []\n        gap = g[t].append\n        if m % 2 == 0:\n            i1, j1 = m >> 1, (M >> 1)+1\n            even = 200000\n            l, r = i1+num, j1+num\n            while l < r:\n                if r % 2 == 0:\n                    r -= 1\n                    even = min(even, tree_even[r])\n                if l % 2 == 0:\n                    even = min(even, tree_even[l])\n                    l += 1\n                l >>= 1\n                r >>= 1\n            even_idx = pos[even]\n            odd = 200000\n            l, r = (even_idx >> 1)+num, j1+num\n            while l < r:\n                if r % 2 == 0:\n                    r -= 1\n                    odd = min(odd, tree_odd[r])\n                if l % 2 == 0:\n                    odd = min(odd, tree_odd[l])\n                    l += 1\n                l >>= 1\n                r >>= 1\n            odd_idx = pos[odd]\n            d[t] = even*n+odd\n            if m != even_idx:\n                s = m*n+even_idx-1\n                qap(s)\n                gap(s)\n            if M != odd_idx:\n                s = (odd_idx+1)*n+M\n                qap(s)\n                gap(s)\n            if even_idx+1 != odd_idx:\n                s = (even_idx+1)*n+odd_idx-1\n                qap(s)\n                gap(s)\n        else:\n            i1, j1 = m >> 1, M >> 1\n            odd = 200000\n            l, r = i1+num, j1+num\n            while l < r:\n                if r % 2 == 0:\n                    r -= 1\n                    odd = min(odd, tree_odd[r])\n                if l % 2 == 0:\n                    odd = min(odd, tree_odd[l])\n                    l += 1\n                l >>= 1\n                r >>= 1\n            odd_idx = pos[odd]\n            even = 200000\n            l, r = (odd_idx >> 1)+1+num, j1+1+num\n            while l < r:\n                if r % 2 == 0:\n                    r -= 1\n                    even = min(even, tree_even[r])\n                if l % 2 == 0:\n                    even = min(even, tree_even[l])\n                    l += 1\n                l >>= 1\n                r >>= 1\n            even_idx = pos[even]\n            d[t] = odd*n+even\n            if m != odd_idx:\n                s = m*n+odd_idx-1\n                qap(s)\n                gap(s)\n            if M != even_idx:\n                s = (even_idx+1)*n+M\n                qap(s)\n                gap(s)\n            if odd_idx+1 != even_idx:\n                s = (odd_idx+1)*n+even_idx-1\n                qap(s)\n                gap(s)\n\n    g2 = dict()\n\n    for i, t in list(g.items()):\n        k = d[i]\n        g2[k] = []\n        ga = g2[k].append\n        for j in t:\n            ga(d[j])\n\n    import heapq\n    h = [d[n-1]]\n    heapq.heapify(h)\n    ans = []\n    hpop = heapq.heappop\n    hpush = heapq.heappush\n\n    while h:\n        t = hpop(h)\n        ans += [t//n+1, t % n+1]\n        if t in g2:\n            for s in g2[t]:\n                hpush(h, s)\n\n    print((*ans))\n\n\nmain()\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: