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 = '# seishin.py\nN = int(input())\n*P, = map(int, input().split())\nM = [0]*(N+1)\nfor i, p in enumerate(P):\n    M[p] = i\n\nINF = 10**9\ndef init(P, n):\n    n0 = 2 ** (n-1).bit_length()\n    data = [INF]*(n0*2)\n    data[n0-1:n0+n-1] = P\n    for i in range(n0-2, -1, -1):\n        data[i] = min(data[2*i+1], data[2*i+2])\n    return data\n\ndef get_data(data, l, r):\n    n0 = len(data)//2\n    l += n0\n    r += n0\n    while l < r:\n        if r&1:\n            r -= 1\n            yield data[r-1]\n        if l&1:\n            yield data[l-1]\n            l += 1\n        l >>= 1\n        r >>= 1\n\ndef get(data, l, r):\n    return min(get_data(data, l, r))\n\nd0 = init(P[0::2], N//2)\nd1 = init(P[1::2], N//2)\n\ndef query_x(l, r):\n    if l % 2 == 0:\n        x = get(d0, l//2, r//2)\n    else:\n        x = get(d1, l//2, r//2)\n    return x\ndef query_y(l, r):\n    if l % 2 == 0:\n        y = get(d1, l//2, r//2)\n    else:\n        y = get(d0, (l+1)//2, (r+1)//2)\n    return y\n\nfrom heapq import heappush, heappop\nque = [(query_x(0, N), 0, N)]\nans = []\nwhile que:\n    x, l, r = heappop(que)\n    if l+2 < r:\n        xi = M[x]\n        y = query_y(xi, r)\n\n        yi = M[y]\n\n        # [l, xi)\n        if l < xi:\n            heappush(que, (query_x(l, xi), l, xi))\n        # [xi+1, yi)\n        if xi+1 < yi:\n            heappush(que, (query_x(xi+1, yi), xi+1, yi))\n        # [yi+1, r)\n        if yi+1 < r:\n            heappush(que, (query_x(yi+1, r), yi+1, r))\n    else:\n        y = P[r-1]\n\n    ans.append("%d %d" % (x, y))\nprint(*ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13511