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 = 'class SegTree:\n    def __init__(self, init_val, ide_ele, segfunc):\n        self.n = len(init_val)\n        self.num =2**(self.n-1).bit_length()\n        self.ide_ele = ide_ele\n        self.seg = [self.ide_ele]*2*self.num\n        self.segfunc = segfunc\n        \n        #set_val\n        for i in range(self.n):\n            self.seg[i+self.num-1] = init_val[i]    \n        #built\n        for i in range(self.num-2,-1,-1) :\n            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) \n    \n    def update(self, k, x):\n        k += self.num-1\n        self.seg[k] = x\n        while k+1:\n            k = (k-1)//2\n            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])\n    \n    def query(self, p, q):\n        if q<=p:\n            return self.ide_ele\n        p += self.num-1\n        q += self.num-2\n        res = self.ide_ele\n        while q-p>1:\n            if p&1 == 0:\n                res = self.segfunc(res, self.seg[p])\n            if q&1 == 1:\n                res = self.segfunc(res, self.seg[q])\n                q -= 1\n            p = p//2\n            q = (q-1)//2\n        if p == q:\n            res = self.segfunc(res, self.seg[p])\n        else:\n            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])\n        return res\n\ndef main():\n    import sys\n    input = sys.stdin.readline\n    \n    N = int(input())\n    P = list(map(int,input().split()))\n    Even = []\n    Odd = []\n    D = {}\n    for i in range(N//2):\n        e = P[2*i]\n        o = P[2*i+1]\n        D[e] = i\n        D[o] = i\n        Even.append(e)\n        Odd.append(o)\n    \n    E_Seg = SegTree(Even,float("inf"),min)\n    O_Seg = SegTree(Odd,float("inf"),min)\n    \n    import heapq\n    heap = []\n    # heapq.heappush(heap, item)\n    # heapq.heappop(heap)\n    \n    def BFS(H):\n        L = H[0]\n        R = H[1]\n        if R <= L:\n            return -1,-1,-1,-1,-1\n        if L%2==0:\n            l = L//2\n            r = R//2\n            mini = E_Seg.query(l,r+1)\n            d_mini = D[mini]\n            mini_b = O_Seg.query(d_mini, r+1)\n            d_mini_b = D[mini_b]\n            \n            leftH = (L, 2*d_mini-1)\n            centH = (2*d_mini+1, 2*d_mini_b)\n            rightH = (2*d_mini_b+2, R)\n            return mini, mini_b, leftH, centH, rightH\n        else:\n            l = L//2\n            r = R//2\n            mini = O_Seg.query(l, r)\n            d_mini = D[mini]\n            mini_b = E_Seg.query(d_mini+1, r+1)\n            d_mini_b = D[mini_b]\n            \n            leftH = (L, 2*d_mini)\n            centH = (2*d_mini+2, 2*d_mini_b-1)\n            rightH = (2*d_mini_b+1, R)\n            return mini, mini_b, leftH, centH, rightH\n        \n    H = (0, N-1)\n    m1,m2,LH,CH,RH = BFS(H)\n    #print(m1,m2)\n    heapq.heappush(heap, [m1,m2,LH,CH,RH])\n    Q = []\n    while heap != []:\n        m1,m2,LH,CH,RH = heapq.heappop(heap)\n        Q += [m1,m2]\n        \n        m1L,m2L,LHL,CHL,RHL = BFS(LH)\n        if m1L != -1:\n            heapq.heappush(heap, [m1L,m2L,LHL,CHL,RHL])\n        \n        m1C,m2C,LHC,CHC,RHC = BFS(CH)\n        if m1C != -1:\n            heapq.heappush(heap, [m1C,m2C,LHC,CHC,RHC])\n        \n        m1R,m2R,LHR,CHR,RHR = BFS(RH)\n        if m1R != -1:\n            heapq.heappush(heap, [m1R,m2R,LHR,CHR,RHR])\n    print(*Q)\n    \n    \n    \n    \nmain()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17855