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\nimport numpy as np\nfrom heapq import heappush, heappop\n\nN = int(input())\nA = np.array(input().split(), dtype=np.int32)\na_to_i = {a:i for i,a in enumerate(A)}\n\n# sparse table を使ってRMQ\n# parityの同じところだけを見るようにしておく\n\nU = len(A).bit_length()\nsp = [None,A]\nfor i in range(2,U):\n    L = 1 << (i-1)\n    sp.append(np.minimum(sp[-1][:-L], sp[-1][L:]))\n\ndef RMQ(x,y):\n    if (y-x)&1: \n        y -= 1\n    # x番目から偶数番目だけ見て[x,y]での最小値を返す\n    d = y - x\n    if d <= 1:\n        return A[x]\n    n = d.bit_length()\n    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])\n\ndef F(x,y):\n    # 辞書式で最小の2つ組をとる\n    # そのあと、今後調べないといけない区間の一覧を返す\n    x1 = RMQ(x,y)\n    i1 = a_to_i[x1]\n    x2 = RMQ(i1+1,y)\n    i2 = a_to_i[x2]\n    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)\n    return x1,x2,task\n\nq = [(None,None,((0,N-1),))]\nanswer = []\nwhile q:\n    x,y,task = heappop(q)\n    if x != None:\n        answer.append(x)\n        answer.append(y)\n    for left,right in task:\n        heappush(q,F(left,right))\n\nprint(' '.join(map(str,answer)))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 6168906