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 = '\n\nclass SegmentTree():\n  def __init__(self,size,f=lambda x,y:x+y,default=0):\n    self.size=pow(2,(size-1).bit_length())\n    self.f=f\n    self.default=default\n    self.data=[default]*(self.size*2)\n  def update(self,i,x):\n    i+=self.size\n    self.data[i]=x\n    while i:\n      i>>=1\n      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])\n  # 区間[l,r)へのクエリ\n  def query(self,l,r):\n    l,r=l+self.size,r+self.size\n    lret,rret=self.default,self.default\n    while l<r:\n      if l&1:\n        lret=self.f(self.data[l],lret)\n        l+=1\n      if r&1:\n        r-=1\n        rret=self.f(self.data[r],rret)\n      l>>=1\n      r>>=1\n    return self.f(lret,rret)\n  def get(self,i):\n    return self.data[self.size+i]\n  def add(self,i,x):\n    self.update(i,self.get(i)+x)\n\nfrom heapq import heappop,heappush\ndef main1(n,p):\n  d={}\n  st0=SegmentTree(n,min,n+1)\n  st1=SegmentTree(n,min,n+1)\n  for i,x in enumerate(p):\n    d[x]=i\n    if i%2==0:\n      st0.update(i,x)\n    else:\n      st1.update(i,x)\n  def func(l,r):\n    if l%2==0:\n      v0=st0.query(l,r)\n      i0=d[v0]\n      v1=st1.query(i0,r)\n    else:\n      v0=st1.query(l,r)\n      i0=d[v0]\n      v1=st0.query(i0,r)\n    return v0,v1,l,r\n  # 区間ごとの辞書順最小先頭を管理：[[v0,v1],[v0,v1,...]\n  ary=[]\n  heappush(ary,func(0,n))\n  ret=[]\n  for _ in range(n//2):\n    v0,v1,l,r=heappop(ary)\n    ret.append(v0)\n    ret.append(v1)\n    i0=d[v0]\n    i1=d[v1]\n    if i0!=l:\n      heappush(ary,func(l,i0))\n    if i0+1!=i1:\n      heappush(ary,func(i0+1,i1))\n    if i1+1!=r:\n      heappush(ary,func(i1+1,r))\n  return ret\n\ndef __starting_point():\n  n=int(input())\n  p=list(map(int,input().split()))\n  ret1=main1(n,p.copy())\n  print((*ret1))\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: