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 = "inf = 10**10\ndef sg_func(a,b):\n    res = [0,0,0]\n    if(a[2]==0):\n        res[0] = min(a[0],b[0])\n        res[1] = min(a[1],b[1])\n    else:\n        res[0] = min(a[0],b[1])\n        res[1] = min(a[1],b[0])\n\n    res[2] = (a[2]+b[2])%2\n\n    return res\n\n\nclass Seg_cus():\n    def __init__(self,x):\n        #####単位元######\n        self.ide_ele_min = inf\n        self.func = sg_func\n\n        self.n = len(x)\n\n        #num_max:n以上の最小の2のべき乗\n        self.num_max =2**(self.n-1).bit_length()\n        self.x = [[self.ide_ele_min,self.ide_ele_min,0] for _  in range(2*self.num_max)]\n\n        for i,num in enumerate(x, self.num_max):\n            self.x[i][0] = num\n            self.x[i][2] = 1\n        for i in range(self.num_max-1,0,-1):\n            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])\n\n    def delete(self,i):\n        i += self.num_max\n        self.x[i][0] = inf\n        self.x[i][2] = 0\n        while(i>0):\n            i = i//2\n            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])\n\n    def query(self,i,j):\n        res = [self.ide_ele_min,self.ide_ele_min,0]\n        if i>=j:\n            return res\n        i += self.num_max\n        j += self.num_max -1\n        stack_i = []\n        stack_j = []\n        while(i<=j):\n            if(i==j):\n                stack_i.append(i)\n                break\n            if(i&1):\n                stack_i.append(i)\n                i += 1\n            if(not j&1):\n                stack_j.append(j)\n                j -= 1\n            i = i>>1\n            j = j>>1\n        for i in stack_i:\n            res = self.func(res,self.x[i])\n        for i in stack_j[::-1]:\n            res = self.func(res,self.x[i])\n\n        return res\n\nclass Seg_min():\n    def __init__(self,x):\n        #####単位元######\n        self.ide_ele_min = 10**10\n        self.func = min\n\n        self.n = len(x)\n\n        #num_max:n以上の最小の2のべき乗\n        self.num_max =2**(self.n-1).bit_length()\n        self.x = [self.ide_ele_min]*2*self.num_max\n\n        for i,num in enumerate(x, self.num_max):\n            self.x[i] = num\n        for i in range(self.num_max-1,0,-1):\n            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])\n\n    def update(self,i,x):\n        i += self.num_max\n        self.x[i] = x\n        while(i>0):\n            i = i//2\n            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])\n\n    def query(self,i,j):\n        res = self.ide_ele_min\n        if i>=j:\n            return res\n        i += self.num_max\n        j += self.num_max -1\n        while(i<=j):\n            if(i==j):\n                res = self.func(res,self.x[i])\n                break\n            if(i&1):\n                res = self.func(res,self.x[i])\n                i += 1\n            if(not j&1):\n                res = self.func(res,self.x[j])\n                j -= 1\n            i = i>>1\n            j = j>>1\n        return res\n\nn = int(input())\np = list(map(int,input().split()))\n\nind = [0] * (n+1)\nfor i,pi in enumerate(p):\n    ind[pi] = i\n\nst = Seg_cus(p)\nst_ind = Seg_min([n] * n)\n\nans = []\nfor _ in range(n//2):\n    num1 = st.query(0,n)[0]\n    num2 = st.query(ind[num1],st_ind.query(ind[num1],n))[1]\n    ans.append(num1)\n    ans.append(num2)\n\n    # print(num1,num2)\n    # print(ind[num1],ind[num2])\n    # print(st.x)\n    # print(st_ind.x)\n    st.delete(ind[num1])\n    st.delete(ind[num2])\n    st_ind.update(ind[num1],ind[num1])\n    st_ind.update(ind[num2],ind[num2])\n\nprint(' '.join(map(str,ans)))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 19877