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\nreadline = sys.stdin.readline\nfrom heapq import heappop as hpp, heappush as hp\nclass Segtree:\n    def __init__(self, A, intv, initialize = True, segf = max):\n        self.N = len(A)\n        self.N0 = 2**(self.N-1).bit_length()\n        self.intv = intv\n        self.segf = segf\n        if initialize:\n            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)\n            for i in range(self.N0-1, 0, -1):\n                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) \n        else:\n            self.data = [intv]*(2*self.N0)\n        \n    def update(self, k, x):\n        k += self.N0\n        self.data[k] = x\n        while k > 0 :\n            k = k >> 1\n            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])\n    \n    def query(self, l, r):\n        L, R = l+self.N0, r+self.N0\n        s = self.intv\n        while L < R:\n            if R & 1:\n                R -= 1\n                s = self.segf(s, self.data[R])\n            if L & 1:\n                s = self.segf(s, self.data[L])\n                L += 1\n            L >>= 1\n            R >>= 1\n        return s\n    \n    def binsearch(self, l, r, check, reverse = False):\n        L, R = l+self.N0, r+self.N0\n        SL, SR = [], []\n        while L < R:\n            if R & 1:\n                R -= 1\n                SR.append(R)\n            if L & 1:\n                SL.append(L)\n                L += 1\n            L >>= 1\n            R >>= 1\n        \n        if reverse:\n            for idx in (SR + SL[::-1]):\n                if check(self.data[idx]):\n                    break\n            else:\n                return -1\n            while idx < self.N0:\n                if check(self.data[2*idx+1]):\n                    idx = 2*idx + 1\n                else:\n                    idx = 2*idx\n            return idx\n        else:\n            for idx in (SL + SR[::-1]):\n                if check(self.data[idx]):\n                    break\n            else:\n                return -1\n            while idx < self.N0:\n                if check(self.data[2*idx]):\n                    idx = 2*idx\n                else:\n                    idx = 2*idx + 1\n            return idx\n\nN = int(readline())\n\ninf = 1<<32\nP = list(map(int, readline().split()))\n\nPi = [None]*(N+1)\nfor i in range(N):\n    Pi[P[i]] = i\n\ninf = 1<<32\nPeven = [P[i] if not i&1 else inf for i in range(N)]\nPodd = [P[i] if i&1 else inf for i in range(N)]\n\nTeven = Segtree(Peven, inf, initialize = True, segf = min)\nTodd = Segtree(Podd, inf, initialize = True, segf = min)\nN0 = 2**(N-1).bit_length()\n\nQ = [(Teven.query(0, N0), 0, N0)]\nfor i in range(N//2):\n    t1, l, r = hpp(Q)\n    K = []\n    if not l&1:\n        p1 = Pi[t1]\n        t2 = Todd.query(p1, r)\n        p2 = Pi[t2]\n        Teven.update(p1, inf)\n        Todd.update(p2, inf)\n    else:\n        p1 = Pi[t1]\n        t2 = Teven.query(p1, r)\n        p2 = Pi[t2]\n        Todd.update(p1, inf)\n        Teven.update(p2, inf)\n    if l < p1:\n        K.append((l, p1))\n    if p2 < r:\n        K.append((p2+1, r))\n    if p1 + 1 < p2:\n        K.append((p1+1, p2))\n    for l, r in K:\n        if not l&1:\n            mq = Teven.query(l, r)\n        else:\n            mq = Todd.query(l, r)\n        hp(Q, (mq, l, r))\n    sys.stdout.write('{} {} '.format(t1, t2))\nsys.stdout.write('\\n')"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17493