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 = 'import heapq\nimport sys\ninput=sys.stdin.readline\n\nclass SegmentTreeMin():\n  def __init__(self,n,init):\n    self.offset=2**((n-1).bit_length())\n    self.tree=[init]*(2*self.offset)\n    self.init=init\n  def update(self,pos,val):\n    pos+=self.offset\n    self.tree[pos]=val\n    while pos>1:\n      pos=pos//2\n      self.tree[pos]=min(self.tree[2*pos],self.tree[2*pos+1])\n  def query(self,l,r):\n    l+=self.offset\n    r+=self.offset\n    ret=self.init\n    while l<=r:\n      ret=min(ret,self.tree[r])\n      r=(r-1)//2\n      ret=min(ret,self.tree[l])\n      l=(l+1)//2\n    return ret\n\nn=int(input())\narr=list(map(int,input().split()))\nodds=SegmentTreeMin(n//2,10**18)\nevens=SegmentTreeMin(n//2,10**18)\ndic={}\nfor i in range(n):\n  dic[arr[i]]=i\n  if i%2==0:\n    odds.update(i//2,arr[i])\n  else:\n    evens.update(i//2,arr[i])\nq=[]\nheapq.heappush(q,(odds.query(0,(n-1)//2),0,n-1))\nans=[]\nwhile len(q)!=0:\n  _,l,r=heapq.heappop(q)\n  if l%2==0:\n    a=odds.query(l//2,r//2)\n    odds.update(dic[a]//2,10**18)\n    b=evens.query(dic[a]//2,r//2)\n    evens.update(dic[b]//2,10**18)\n    ans.append(a)\n    ans.append(b)\n    tl=dic[a]\n    tr=dic[b]\n    if tl!=l:\n      heapq.heappush(q,(odds.query(l//2,(tl-1)//2),l,tl-1))\n    if tl+1<tr-1:\n      heapq.heappush(q,(evens.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))\n    if tr!=r:\n      heapq.heappush(q,(odds.query((tr+1)//2,r//2),tr+1,r))\n  else:\n    a=evens.query(l//2,r//2)\n    evens.update(dic[a]//2,10**18)\n    b=odds.query((dic[a]+1)//2,r//2)\n    odds.update(dic[b]//2,10**18)\n    ans.append(a)\n    ans.append(b)\n    tl=dic[a]\n    tr=dic[b]\n    if tl!=l:\n      heapq.heappush(q,(evens.query(l//2,(tl-1)//2),l,tl-1))\n    if tl+1<tr-1:\n      heapq.heappush(q,(odds.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))\n    if tr!=r:\n      heapq.heappush(q,(evens.query((tr+1)//2,r//2),tr+1,r))\nprint(*ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18145