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 collections import deque\nimport heapq\nimport sys\ninput = sys.stdin.readline\n\n\nclass SparseTable():\n    """区間取得クエリをO(1)で答えるデータ構造をO(NlogN)で構築する\n    query(l, r): 区間[l, r)に対するクエリに答える\n    """\n    def __init__(self, array, n):\n        n = len(array)\n        self.row_size = n.bit_length()\n\n        # log_tableを構築する\n        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]\n        self.log_table = [0] * (n + 1)\n        for i in range(2, n + 1):\n            self.log_table[i] = self.log_table[i//2] + 1\n\n        # sparse_tableを構築する\n        self.sparse_table = [[0] * n for _ in range(self.row_size)]\n        for i in range(n):\n            self.sparse_table[0][i] = array[i]\n        for row in range(1, self.row_size):\n            for i in range(n - (1 << row) + 1):\n                self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \\\n                                            self.sparse_table[row - 1][i + (1 << row - 1)])\n\n    def _merge(self, num1, num2):\n        """クエリの内容"""\n        return min(num1, num2)\n\n    def query(self, l, r):\n        """区間[l, r)に対するクエリに答える"""\n        row = self.log_table[r - l]\n        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])\n\n\nn = int(input())\np = list(map(int, input().split()))\n\nq = [[0] * (n // 2) for i in range(2)]\n\nfor i in range(n):\n    q[i%2][i//2] = p[i]\n\nind = {}\nfor i in range(n):\n    ind[p[i]] = i\n\nsp0 = SparseTable(q[0], n // 2)\nsp1 = SparseTable(q[1], n // 2)\n\ncon = {}\nans = {}\ndiv = 10**6\ndef solve(l, r):\n    q = deque([l * div + r])\n    while q:\n        pos = q.pop()\n        l, r = pos // div, pos % div \n        # min1 = min(q[l%2][l//2:r//2])\n        if l % 2 == 0:\n            min1 = sp0.query(l//2, r//2)\n        else:\n            min1 = sp1.query(l//2, r//2)\n        use_pos1 = ind[min1]\n        \n        # min2 = min(q[(l+1)%2][(use_pos1+1)//2:(r+1)//2])\n        if (l + 1) % 2 == 0:\n            min2 = sp0.query((use_pos1 + 1) // 2, (r + 1) // 2)\n        else:\n            min2 = sp1.query((use_pos1 + 1) // 2, (r + 1) // 2)\n        use_pos2 =  ind[min2]\n        \n        ans[pos] = min1 * div + min2\n        con[pos] = []\n        if l != use_pos1:\n            con[pos].append(l * div + use_pos1)\n            q.append(l * div + use_pos1)\n        if use_pos1 + 1 != use_pos2:\n            con[pos].append((use_pos1 + 1) * div + use_pos2)\n            q.append((use_pos1 + 1) * div + use_pos2)\n        if use_pos2 + 1 != r:\n            con[pos].append((use_pos2 + 1) * div + r)\n            q.append((use_pos2 + 1) * div + r)\n\n    return\n\n\nsolve(0, n)\nres = []\nq = [(ans[n], n)]\nwhile q:\n    num, i = heapq.heappop(q)\n    min1, min2 = num // div, num % div\n    res.append(min1)\n    res.append(min2)\n    for new_num in con[i]:\n        heapq.heappush(q, (ans[new_num], new_num))\nprint(*res)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 17443