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 = 'from heapq import heappop, heappush\nimport sys\nsys.setrecursionlimit(10 ** 7)\ninput = sys.stdin.readline\n\nn = int(input())\np = [int(x) for x in input().split()]\n\n\nclass SegmentTree:  # 0-indexed\n    def __init__(self, array, operation=min, identity=10**30):\n        self.identity = identity\n        self.n = len(array)\n        self.N = 1 << (self.n - 1).bit_length()\n        self.tree = [self.identity] * 2 * self.N\n        self.opr = operation\n        for i in range(self.n):\n            self.tree[i+self.N-1] = array[i]\n        for i in range(self.N-2, -1, -1):\n            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])\n\n    def values(self):\n        return self.tree[self.N-1:]\n\n    def update(self, k, x):\n        k += self.N-1\n        self.tree[k] = x\n        while k+1:\n            k = (k-1)//2\n            self.tree[k] = self.opr(self.tree[k*2+1], self.tree[k*2+2])\n\n    def query(self, p, q):  # [p,q)\n        if q <= p:\n            print("Oops!  That was no valid number.  Try again...")\n            return\n        p += self.N-1\n        q += self.N-2\n        res = self.identity\n        while q-p > 1:\n            if p & 1 == 0:\n                res = self.opr(res, self.tree[p])\n            if q & 1 == 1:\n                res = self.opr(res, self.tree[q])\n                q -= 1\n            p = p//2\n            q = (q-1)//2\n        if p == q:\n            res = self.opr(res, self.tree[p])\n        else:\n            res = self.opr(self.opr(res, self.tree[p]), self.tree[q])\n        return res\n\n\nind = [0]*(n+1)\nOdd = SegmentTree([10**30]*n)\nEven = SegmentTree([10**30]*n)\n\nfor i in range(n):\n    ind[p[i]] = i\n    if i % 2 == 0:\n        Even.update(i, p[i])\n    else:\n        Odd.update(i, p[i])\n\ncand = []\nheappush(cand, (Even.query(0, n), 0, n, True))\n\nq = []\nwhile len(q) < n:\n    first, l, r, is_even = heappop(cand)\n    if is_even:\n        second = Odd.query(ind[first]+1, r)\n        q.extend([first, second])\n        if l < ind[first]:\n            heappush(cand, (Even.query(l, ind[first]), l, ind[first], True))\n        if ind[first] + 1 < ind[second]:\n            heappush(\n                cand, (Odd.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], False))\n        if ind[second]+1 < r:\n            heappush(\n                cand, (Even.query(ind[second], r), ind[second]+1, r, True))\n    else:\n        second = Even.query(ind[first]+1, r)\n        q.extend([first, second])\n        if l < ind[first]:\n            heappush(cand, (Odd.query(l, ind[first]), l, ind[first], False))\n        if ind[first] + 1 < ind[second]:\n            heappush(\n                cand, (Even.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], True))\n        if ind[second]+1 < r:\n            heappush(\n                cand, (Odd.query(ind[second], r), ind[second]+1, r, False))\n\nprint((*q))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: