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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\ngosa = 1.0 / 10**10\nmod = 10**9+7\n\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]\ndef LF(): return [float(x) for x in sys.stdin.readline().split()]\ndef LS(): return sys.stdin.readline().split()\ndef I(): return int(sys.stdin.readline())\ndef F(): return float(sys.stdin.readline())\ndef S(): return input()\n\nclass Seg():\n    def __init__(self, na, default, func):\n        if isinstance(na, list):\n            n = len(na)\n        else:\n            n = na\n        i = 1\n        while 2**i <= n:\n            i += 1\n        self.D = default\n        self.H = i\n        self.N = 2**i\n        if isinstance(na, list):\n            self.A = [default] * (self.N) + na + [default] * (self.N-n)\n            for i in range(self.N-1,0,-1):\n                self.A[i] = func(self.A[i*2], self.A[i*2+1])\n        else:\n            self.A = [default] * (self.N*2)\n        self.F = func\n\n    def find(self, i):\n        return self.A[i + self.N]\n\n    def update(self, i, x):\n        i += self.N\n        self.A[i] = x\n        while i > 0:\n            i = (i-1) // 2\n            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])\n\n    def merge(self, a, b):\n        return self.F(a, b)\n\n    def total(self):\n        return self.A[0]\n\n    def query(self, a, b):\n        A = self.A\n        l = a + self.N\n        r = b + self.N\n        res = self.D\n        while l < r:\n            if l % 2 == 1:\n                res = self.merge(res, A[l])\n                l += 1\n            if r % 2 == 1:\n                r -= 1\n                res = self.merge(res, A[r])\n            l >>= 1\n            r >>= 1\n\n        return res\n\ndef main():\n    n = I()\n    a = LI()\n\n    def sf(a,b):\n        if a < b:\n            return a\n        return b\n\n    s1 = Seg([c if i%2==0 else inf for c,i in zip(a,list(range(n)))],inf,sf)\n    s2 = Seg([c if i%2==1 else inf for c,i in zip(a,list(range(n)))],inf,sf)\n    d = {}\n\n    for i in range(n):\n        d[a[i]] = i\n\n    def f(l,r):\n        if l % 2 == 0:\n            t = s1.query(l,r)\n            ti = d[t]\n            u = s2.query(ti+1,r)\n        else:\n            t = s2.query(l,r)\n            ti = d[t]\n            u = s1.query(ti+1,r)\n        ui = d[u]\n        nl = []\n        if l < ti:\n            nl.append((l, ti))\n        if ui - ti > 1:\n            nl.append((ti+1, ui))\n        if ui < r-1:\n            nl.append((ui+1, r))\n        return ((t,u), nl)\n\n    q = []\n    heapq.heappush(q, f(0,n))\n    r = []\n    while q:\n        t,nl = heapq.heappop(q)\n        r.append(t[0])\n        r.append(t[1])\n        for t,u in nl:\n            heapq.heappush(q, f(t,u))\n\n    return ' '.join(map(str,r))\n\nprint((main()))\n\n\n\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 181663