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\nINF = 10**30\n\nclass Rmin():\n\tdef __init__(self, size):\n\t\t#the number of nodes is 2n-1\n\t\tself.n = 1\n\t\twhile self.n < size:\n\t\t\tself.n *= 2\n\t\tself.node = [INF] * (2*self.n-1)\n\n\tdef Access(self, x):\n\t\treturn self.node[x+self.n-1]\n\n\tdef Update(self, x, val):\n\t\tx += self.n-1\n\t\tself.node[x] = val\n\t\twhile x > 0:\n\t\t\tx = (x-1)//2\n\t\t\tself.node[x] = min(self.node[2*x+1], self.node[2*x+2])\n\t\treturn\n\n\t#[l, r)\n\tdef Get(self, l, r):\n\t\tL, R = l+self.n, r+self.n\n\t\ts = INF\n\t\twhile L < R:\n\t\t\tif R & 1:\n\t\t\t\tR -= 1\n\t\t\t\ts = min(s, self.node[R-1])\t\t\t\n\t\t\tif L & 1:\n\t\t\t\ts = min(s, self.node[L-1])\n\t\t\t\tL += 1\n\t\t\tL >>= 1\n\t\t\tR >>= 1\n\t\treturn s\n\nn = int(input())\na = list(map(int, input().split()))\n\neven, odd = Rmin(n), Rmin(n)\nfor i in range(n):\n\tif i%2 == 0:\n\t\teven.Update(i, a[i]*(10**7) + i)\n\telse:\n\t\todd.Update(i, a[i]*(10**7) + i)\n\nd = dict()\n\ndef search(l, r):\n\tif l%2 == 0:\n\t\tp = even.Get(l, r+1)\n\t\tq = odd.Get(p%(10**7)+1, r+1)\n\telse:\n\t\tp = odd.Get(l, r+1)\n\t\tq = even.Get(p%(10**7)+1, r+1)\n\treturn p, q\n\nx, y = search(0, n-1)\nd[x%(10**7)] = (y, 0, n-1)\nque = [x]\nans = []\n\nwhile que:\n\tx = heappop(que)\n\ty, l, r = d[x%(10**7)]\n\tans += [x//(10**7), y//(10**7)]\n\n\tif l != x%(10**7):\n\t\tp, q = search(l, x%(10**7)-1)\n\t\td[p%(10**7)] = (q, l, x%(10**7)-1)\n\t\theappush(que, p)\n\n\tif r != y%(10**7):\n\t\tp, q = search(y%(10**7)+1, r)\n\t\td[p%(10**7)] = (q, y%(10**7)+1, r)\n\t\theappush(que, p)\n\n\tif x%(10**7)+1 != y%(10**7):\n\t\tp, q = search(x%(10**7)+1, y%(10**7)-1)\n\t\td[p%(10**7)] = (q, x%(10**7)+1, y%(10**7)-1)\n\t\theappush(que, p)\n\nprint(*ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 16919