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)

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline
import numpy as np
from heapq import heappush, heappop

N = int(input())
A = np.array(input().split(), dtype=np.int32)
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append(np.minimum(sp[-1][:-L], sp[-1][L:]))

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))



class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  # 区間[l,r)へのクエリ
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)

from heapq import heappop,heappush
def main1(n,p):
  d={}
  st0=SegmentTree(n,min,n+1)
  st1=SegmentTree(n,min,n+1)
  for i,x in enumerate(p):
    d[x]=i
    if i%2==0:
      st0.update(i,x)
    else:
      st1.update(i,x)
  def func(l,r):
    if l%2==0:
      v0=st0.query(l,r)
      i0=d[v0]
      v1=st1.query(i0,r)
    else:
      v0=st1.query(l,r)
      i0=d[v0]
      v1=st0.query(i0,r)
    return v0,v1,l,r
  # 区間ごとの辞書順最小先頭を管理：[[v0,v1],[v0,v1,...]
  ary=[]
  heappush(ary,func(0,n))
  ret=[]
  for _ in range(n//2):
    v0,v1,l,r=heappop(ary)
    ret.append(v0)
    ret.append(v1)
    i0=d[v0]
    i1=d[v1]
    if i0!=l:
      heappush(ary,func(l,i0))
    if i0+1!=i1:
      heappush(ary,func(i0+1,i1))
    if i1+1!=r:
      heappush(ary,func(i1+1,r))
  return ret

def __starting_point():
  n=int(input())
  p=list(map(int,input().split()))
  ret1=main1(n,p.copy())
  print((*ret1))

__starting_point()

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n = I()
    a = LI()

    def sf(a,b):
        if a < b:
            return a
        return b

    s1 = Seg([c if i%2==0 else inf for c,i in zip(a,list(range(n)))],inf,sf)
    s2 = Seg([c if i%2==1 else inf for c,i in zip(a,list(range(n)))],inf,sf)
    d = {}

    for i in range(n):
        d[a[i]] = i

    def f(l,r):
        if l % 2 == 0:
            t = s1.query(l,r)
            ti = d[t]
            u = s2.query(ti+1,r)
        else:
            t = s2.query(l,r)
            ti = d[t]
            u = s1.query(ti+1,r)
        ui = d[u]
        nl = []
        if l < ti:
            nl.append((l, ti))
        if ui - ti > 1:
            nl.append((ti+1, ui))
        if ui < r-1:
            nl.append((ui+1, r))
        return ((t,u), nl)

    q = []
    heapq.heappush(q, f(0,n))
    r = []
    while q:
        t,nl = heapq.heappop(q)
        r.append(t[0])
        r.append(t[1])
        for t,u in nl:
            heapq.heappush(q, f(t,u))

    return ' '.join(map(str,r))

print((main()))





import sys
input = sys.stdin.readline

# O(NlogN)構築、クエリO(1)のRMQ
# 変更はできない
class SparseTable():
    def __init__(self, N, A):
        self.N = N
        self.logN = N.bit_length()
        self.A = A
        self.table = [[i for i in range(N)]]
        for k in range(self.logN):
            tab = []
            for i in range(self.N-(1<<(k+1))+1):
                ind1 = self.table[-1][i]
                ind2 = self.table[-1][i+(1<<k)]
                if self.A[ind1] <= self.A[ind2]:
                    tab.append(ind1)
                else:
                    tab.append(ind2)
            self.table.append(tab)
    
    # [l, r)のminの(val, key)
    def query_min(self, l, r):
        k = (r-l).bit_length()-1
        indl = self.table[k][l]
        indr = self.table[k][r-(1<<k)]
        if self.A[indl] <= self.A[indr]:
            return self.A[indl], indl
        return self.A[indr], indr

import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
    SP1 = SparseTable((N+1)//2, A[::2])
    SP2 = SparseTable(N//2, A[1::2])

    ans = []
    q = []
    v, k = SP1.query_min(0, N//2)
    dic = {}
    dic[v] = (k, 0, N//2, True)
    hp.heappush(q, v)
    for _ in range(N//2):
        valuea = hp.heappop(q)
        ka, l, r, is1 = dic[valuea]
        ans.append(str(valuea))
        if is1:
            valueb, kb = SP2.query_min(ka, r)
            if ka < kb:
                m2, nk2 = SP2.query_min(ka, kb)
                hp.heappush(q, m2)
                dic[m2] = (nk2, ka, kb+1, False)
            if l < ka:
                m1, nk1 = SP1.query_min(l, ka)
                hp.heappush(q, m1)
                dic[m1] = (nk1, l, ka, True)
            if kb+1 < r:
                m3, nk3 = SP1.query_min(kb+1, r)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb+1, r, True)
        else:
            valueb, kb = SP1.query_min(ka+1, r)
            if ka+1 < kb:
                m1, nk1 = SP1.query_min(ka+1, kb)
                hp.heappush(q, m1)
                dic[m1] = (nk1, ka+1, kb, True)
            if l < ka:
                m2, nk2 = SP2.query_min(l, ka)
                hp.heappush(q, m2)
                dic[m2] = (nk2, l, ka+1, False)
            if kb < r-1:
                m3, nk3 = SP2.query_min(kb, r-1)
                hp.heappush(q, m3)
                dic[m3] = (nk3, kb, r, False)

        ans.append(str(valueb))

    print(" ".join(ans))


def __starting_point():
    main()
__starting_point()

#####segfunc#####
def segfunc(x, y):
    if y[0]>x[0]:
        return x
    else:
        return y
#################

#####ide_ele#####
ide_ele =(float("inf"),-1)
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import heapq

N=int(input())
p=list(map(int,input().split()))
n=N//2
op=[(p[2*i+1],2*i+1) for i in range(n)]
ep=[(p[2*i],2*i) for i in range(n)]

oseg=SegTree(op,segfunc,ide_ele)
eseg=SegTree(ep,segfunc,ide_ele)

def first(l,r):
    if l>=r:
        return (-1,-1,-1,-1)
    if l%2==0:
        val,index=eseg.query(l//2,r//2)
        val2,index2=oseg.query(index//2,r//2)
        return (val,val2,index,index2)
    else:
        val,index=oseg.query(l//2,r//2)
        val2,index2=eseg.query(index//2+1,r//2+1)
        return (val,val2,index,index2)

val,val2,index,index2=first(0,N)
que=[((val,val2),0,N)]
heapq.heapify(que)
ans=[]
while que:
    tuple,l,r=heapq.heappop(que)
    ans.append(tuple[0])
    ans.append(tuple[1])
    val,val2,index,index2=first(l,r)
    val,val2,l1,r1=first(l,index)
    if val!=-1:
        heapq.heappush(que,((val,val2),l,index))
    val,val2,l2,r2=first(index+1,index2)
    if val!=-1:
        heapq.heappush(que,((val,val2),index+1,index2))
    val,val2,l3,r3=first(index2+1,r)
    if val!=-1:
        heapq.heappush(que,((val,val2),index2+1,r))

print(*ans)

def main():
    n = int(input())
    p = list([int(x)-1 for x in input().split()])

    pos = [j for i, j in sorted([(j, i) for i, j in enumerate(p)])]
    basesize = n >> 1
    num = 1
    while num < basesize:
        num *= 2
    num -= 1

    tree_even = [100001]*(num*2+1)
    tree_odd = [100001]*(num*2+1)

    for i in range(num, num+basesize):
        tree_even[i] = p[(i-num)*2]
    for i in range(num-1, -1, -1):
        tree_even[i] = min(tree_even[2*i+1:2*i+3])
    for i in range(num, num+basesize):
        tree_odd[i] = p[(i-num)*2+1]
    for i in range(num-1, -1, -1):
        tree_odd[i] = min(tree_odd[2*i+1:2*i+3])

    g = dict()
    d = dict()
    q = [n-1]
    qap, qp = q.append, q.pop
    while q:
        t = qp()
        m, M = t//n, t % n
        if m+1 == M:
            d[t] = p[m]*n+p[M]
            continue
        g[t] = []
        gap = g[t].append
        if m % 2 == 0:
            i1, j1 = m >> 1, (M >> 1)+1
            even = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            odd = 200000
            l, r = (even_idx >> 1)+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            d[t] = even*n+odd
            if m != even_idx:
                s = m*n+even_idx-1
                qap(s)
                gap(s)
            if M != odd_idx:
                s = (odd_idx+1)*n+M
                qap(s)
                gap(s)
            if even_idx+1 != odd_idx:
                s = (even_idx+1)*n+odd_idx-1
                qap(s)
                gap(s)
        else:
            i1, j1 = m >> 1, M >> 1
            odd = 200000
            l, r = i1+num, j1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    odd = min(odd, tree_odd[r])
                if l % 2 == 0:
                    odd = min(odd, tree_odd[l])
                    l += 1
                l >>= 1
                r >>= 1
            odd_idx = pos[odd]
            even = 200000
            l, r = (odd_idx >> 1)+1+num, j1+1+num
            while l < r:
                if r % 2 == 0:
                    r -= 1
                    even = min(even, tree_even[r])
                if l % 2 == 0:
                    even = min(even, tree_even[l])
                    l += 1
                l >>= 1
                r >>= 1
            even_idx = pos[even]
            d[t] = odd*n+even
            if m != odd_idx:
                s = m*n+odd_idx-1
                qap(s)
                gap(s)
            if M != even_idx:
                s = (even_idx+1)*n+M
                qap(s)
                gap(s)
            if odd_idx+1 != even_idx:
                s = (odd_idx+1)*n+even_idx-1
                qap(s)
                gap(s)

    g2 = dict()

    for i, t in list(g.items()):
        k = d[i]
        g2[k] = []
        ga = g2[k].append
        for j in t:
            ga(d[j])

    import heapq
    h = [d[n-1]]
    heapq.heapify(h)
    ans = []
    hpop = heapq.heappop
    hpush = heapq.heappush

    while h:
        t = hpop(h)
        ans += [t//n+1, t % n+1]
        if t in g2:
            for s in g2[t]:
                hpush(h, s)

    print((*ans))


main()


# seishin.py
N = int(input())
*P, = map(int, input().split())
M = [0]*(N+1)
for i, p in enumerate(P):
    M[p] = i

INF = 10**9
def init(P, n):
    n0 = 2 ** (n-1).bit_length()
    data = [INF]*(n0*2)
    data[n0-1:n0+n-1] = P
    for i in range(n0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    return data

def get_data(data, l, r):
    n0 = len(data)//2
    l += n0
    r += n0
    while l < r:
        if r&1:
            r -= 1
            yield data[r-1]
        if l&1:
            yield data[l-1]
            l += 1
        l >>= 1
        r >>= 1

def get(data, l, r):
    return min(get_data(data, l, r))

d0 = init(P[0::2], N//2)
d1 = init(P[1::2], N//2)

def query_x(l, r):
    if l % 2 == 0:
        x = get(d0, l//2, r//2)
    else:
        x = get(d1, l//2, r//2)
    return x
def query_y(l, r):
    if l % 2 == 0:
        y = get(d1, l//2, r//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y

from heapq import heappush, heappop
que = [(query_x(0, N), 0, N)]
ans = []
while que:
    x, l, r = heappop(que)
    if l+2 < r:
        xi = M[x]
        y = query_y(xi, r)

        yi = M[y]

        # [l, xi)
        if l < xi:
            heappush(que, (query_x(l, xi), l, xi))
        # [xi+1, yi)
        if xi+1 < yi:
            heappush(que, (query_x(xi+1, yi), xi+1, yi))
        # [yi+1, r)
        if yi+1 < r:
            heappush(que, (query_x(yi+1, r), yi+1, r))
    else:
        y = P[r-1]

    ans.append("%d %d" % (x, y))
print(*ans)

import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

N = int(readline())

inf = 1<<32
P = list(map(int, readline().split()))

Pi = [None]*(N+1)
for i in range(N):
    Pi[P[i]] = i

inf = 1<<32
Peven = [P[i] if not i&1 else inf for i in range(N)]
Podd = [P[i] if i&1 else inf for i in range(N)]

Teven = Segtree(Peven, inf, initialize = True, segf = min)
Todd = Segtree(Podd, inf, initialize = True, segf = min)
N0 = 2**(N-1).bit_length()

Q = [(Teven.query(0, N0), 0, N0)]
for i in range(N//2):
    t1, l, r = hpp(Q)
    K = []
    if not l&1:
        p1 = Pi[t1]
        t2 = Todd.query(p1, r)
        p2 = Pi[t2]
        Teven.update(p1, inf)
        Todd.update(p2, inf)
    else:
        p1 = Pi[t1]
        t2 = Teven.query(p1, r)
        p2 = Pi[t2]
        Todd.update(p1, inf)
        Teven.update(p2, inf)
    if l < p1:
        K.append((l, p1))
    if p2 < r:
        K.append((p2+1, r))
    if p1 + 1 < p2:
        K.append((p1+1, p2))
    for l, r in K:
        if not l&1:
            mq = Teven.query(l, r)
        else:
            mq = Todd.query(l, r)
        hp(Q, (mq, l, r))
    sys.stdout.write('{} {} '.format(t1, t2))
sys.stdout.write('\n')

inf = 10**10
def sg_func(a,b):
    res = [0,0,0]
    if(a[2]==0):
        res[0] = min(a[0],b[0])
        res[1] = min(a[1],b[1])
    else:
        res[0] = min(a[0],b[1])
        res[1] = min(a[1],b[0])

    res[2] = (a[2]+b[2])%2

    return res


class Seg_cus():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = inf
        self.func = sg_func

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [[self.ide_ele_min,self.ide_ele_min,0] for _  in range(2*self.num_max)]

        for i,num in enumerate(x, self.num_max):
            self.x[i][0] = num
            self.x[i][2] = 1
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def delete(self,i):
        i += self.num_max
        self.x[i][0] = inf
        self.x[i][2] = 0
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = [self.ide_ele_min,self.ide_ele_min,0]
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        stack_i = []
        stack_j = []
        while(i<=j):
            if(i==j):
                stack_i.append(i)
                break
            if(i&1):
                stack_i.append(i)
                i += 1
            if(not j&1):
                stack_j.append(j)
                j -= 1
            i = i>>1
            j = j>>1
        for i in stack_i:
            res = self.func(res,self.x[i])
        for i in stack_j[::-1]:
            res = self.func(res,self.x[i])

        return res

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

n = int(input())
p = list(map(int,input().split()))

ind = [0] * (n+1)
for i,pi in enumerate(p):
    ind[pi] = i

st = Seg_cus(p)
st_ind = Seg_min([n] * n)

ans = []
for _ in range(n//2):
    num1 = st.query(0,n)[0]
    num2 = st.query(ind[num1],st_ind.query(ind[num1],n))[1]
    ans.append(num1)
    ans.append(num2)

    # print(num1,num2)
    # print(ind[num1],ind[num2])
    # print(st.x)
    # print(st_ind.x)
    st.delete(ind[num1])
    st.delete(ind[num2])
    st_ind.update(ind[num1],ind[num1])
    st_ind.update(ind[num2],ind[num2])

print(' '.join(map(str,ans)))

from heapq import heappop, heappush
n = int(input())
p = [int(x) for x in input().split()]


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:]

    def update(self, k, x):
        k += self.N-1
        self.tree[k] = x
        while k+1:
            k = (k-1)//2
            self.tree[k] = self.opr(self.tree[k*2+1], self.tree[k*2+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            return
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 1:
            if p & 1 == 0:
                res = self.opr(res, self.tree[p])
            if q & 1 == 1:
                res = self.opr(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.opr(res, self.tree[p])
        else:
            res = self.opr(self.opr(res, self.tree[p]), self.tree[q])
        return res


ind = [0]*(n+1)
Odd = SegmentTree([10**30]*n)
Even = SegmentTree([10**30]*n)

for i in range(n):
    ind[p[i]] = i
    if i % 2 == 0:
        Even.update(i, p[i])
    else:
        Odd.update(i, p[i])

cand = []
heappush(cand, (Even.query(0, n), 0, n, True))

q = []
for _ in range(n//2):
    first, l, r, is_even = heappop(cand)
    if is_even:
        second = Odd.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Even.query(l, ind[first]), l, ind[first], True))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Odd.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], False))
        if ind[second]+1 < r:
            heappush(
                cand, (Even.query(ind[second], r), ind[second]+1, r, True))
    else:
        second = Even.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Odd.query(l, ind[first]), l, ind[first], False))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Even.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], True))
        if ind[second]+1 < r:
            heappush(
                cand, (Odd.query(ind[second], r), ind[second]+1, r, False))

print((*q))


from heapq import heappop, heappush
n = int(input())
p = [int(x) for x in input().split()]


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:]

    def update(self, k, x):
        k += self.N-1
        self.tree[k] = x
        while k+1:
            k = (k-1)//2
            self.tree[k] = self.opr(self.tree[k*2+1], self.tree[k*2+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            return
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 1:
            if p & 1 == 0:
                res = self.opr(res, self.tree[p])
            if q & 1 == 1:
                res = self.opr(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.opr(res, self.tree[p])
        else:
            res = self.opr(self.opr(res, self.tree[p]), self.tree[q])
        return res


ind = [0]*(n+1)
Odd = SegmentTree([10**30]*n)
Even = SegmentTree([10**30]*n)

for i in range(n):
    ind[p[i]] = i
    if i % 2 == 0:
        Even.update(i, p[i])
    else:
        Odd.update(i, p[i])

cand = []
heappush(cand, (Even.query(0, n), 0, n, True))

q = []
while len(q) < n:
    first, l, r, is_even = heappop(cand)
    if is_even:
        second = Odd.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Even.query(l, ind[first]), l, ind[first], True))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Odd.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], False))
        if ind[second]+1 < r:
            heappush(
                cand, (Even.query(ind[second], r), ind[second]+1, r, True))
    else:
        second = Even.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Odd.query(l, ind[first]), l, ind[first], False))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Even.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], True))
        if ind[second]+1 < r:
            heappush(
                cand, (Odd.query(ind[second], r), ind[second]+1, r, False))

print((*q))


# seishin.py
N = int(input())
*P, = map(int, input().split())
M = [0]*(N+1)
for i, p in enumerate(P):
    M[p] = i

INF = 10**9
def init(P, n):
    n0 = 2 ** (n-1).bit_length()
    data = [INF]*(n0*2)
    data[n0-1:n0+n-1] = P
    for i in range(n0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    return data

def get_data(data, l, r):
    n0 = len(data)//2
    l += n0
    r += n0
    while l < r:
        if r&1:
            r -= 1
            yield data[r-1]
        if l&1:
            yield data[l-1]
            l += 1
        l >>= 1
        r >>= 1

def get(data, l, r):
    return min(get_data(data, l, r))

d0 = init(P[0::2], N//2)
d1 = init(P[1::2], N//2)

def query_x(l, r):
    if l % 2 == 0:
        x = get(d0, l//2, r//2)
    else:
        x = get(d1, l//2, r//2)
    return x
def query_y(l, r):
    if l % 2 == 0:
        y = get(d1, l//2, r//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y

from heapq import heappush, heappop
que = [(query_x(0, N), 0, N)]
ans = []
while que:
    x, l, r = heappop(que)
    if l+2 < r:
        xi = M[x]
        y = query_y(xi, r)

        yi = M[y]

        # [l, xi)
        if l < xi:
            heappush(que, (query_x(l, xi), l, xi))
        # [xi+1, yi)
        if xi+1 < yi:
            heappush(que, (query_x(xi+1, yi), xi+1, yi))
        # [yi+1, r)
        if yi+1 < r:
            heappush(que, (query_x(yi+1, r), yi+1, r))
    else:
        y = P[r-1]

    ans.append("%d %d" % (x, y))
print(*ans)

# seishin.py
N = int(input())
*P, = map(int, input().split())
M = [0]*(N+1)
for i, p in enumerate(P):
    M[p] = i

INF = 10**9
def init(P, n):
    n0 = 2 ** (n-1).bit_length()
    data = [INF]*(n0*2)
    data[n0-1:n0+n-1] = P
    for i in range(n0-2, -1, -1):
        data[i] = min(data[2*i+1], data[2*i+2])
    return data

"""
def __get(data, a, b, k, l, r):
    if a <= l and r <= b:
        return data[k]
    if b <= l or r <= a:
        return INF
    vl = __get(data, a, b, 2*k+1, l, (l+r)//2)
    vr = __get(data, a, b, 2*k+2, (l+r)//2, r)
    return min(vl, vr)
"""

def get_data(data, l, r):
    n0 = len(data)//2
    l += n0
    r += n0
    while l < r:
        if r&1:
            r -= 1
            yield data[r-1]
        if l&1:
            yield data[l-1]
            l += 1
        l >>= 1
        r >>= 1
    yield INF

def get(data, l, r):
    #return __get(data, l, r, 0, 0, len(data)//2)
    return min(get_data(data, l, r))

d0 = init(P[0::2], N//2)
d1 = init(P[1::2], N//2)

def query_x(l, r):
    if l % 2 == 0:
        x = get(d0, l//2, r//2)
    else:
        x = get(d1, l//2, r//2)
    return x
def query_y(l, r):
    if l % 2 == 0:
        y = get(d1, l//2, r//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y

from heapq import heappush, heappop
que = [(query_x(0, N), 0, N)]
ans = []
while que:
    x, l, r = heappop(que)
    if l+2 < r:
        xi = M[x]
        y = query_y(xi, r)

        yi = M[y]

        # [l, xi)
        if l < xi:
            heappush(que, (query_x(l, xi), l, xi))
        # [xi+1, yi)
        if xi+1 < yi:
            heappush(que, (query_x(xi+1, yi), xi+1, yi))
        # [yi+1, r)
        if yi+1 < r:
            heappush(que, (query_x(yi+1, r), yi+1, r))
    else:
        y = P[r-1]

    ans.append("%d %d" % (x, y))
print(*ans)

import heapq
import sys
input=sys.stdin.readline

class SegmentTreeMin():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=min(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=min(ret,self.tree[r])
      r=(r-1)//2
      ret=min(ret,self.tree[l])
      l=(l+1)//2
    return ret

n=int(input())
arr=list(map(int,input().split()))
odds=SegmentTreeMin(n//2,10**18)
evens=SegmentTreeMin(n//2,10**18)
dic={}
for i in range(n):
  dic[arr[i]]=i
  if i%2==0:
    odds.update(i//2,arr[i])
  else:
    evens.update(i//2,arr[i])
q=[]
heapq.heappush(q,(odds.query(0,(n-1)//2),0,n-1))
ans=[]
while len(q)!=0:
  _,l,r=heapq.heappop(q)
  if l%2==0:
    a=odds.query(l//2,r//2)
    odds.update(dic[a]//2,10**18)
    b=evens.query(dic[a]//2,r//2)
    evens.update(dic[b]//2,10**18)
    ans.append(a)
    ans.append(b)
    tl=dic[a]
    tr=dic[b]
    if tl!=l:
      heapq.heappush(q,(odds.query(l//2,(tl-1)//2),l,tl-1))
    if tl+1<tr-1:
      heapq.heappush(q,(evens.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if tr!=r:
      heapq.heappush(q,(odds.query((tr+1)//2,r//2),tr+1,r))
  else:
    a=evens.query(l//2,r//2)
    evens.update(dic[a]//2,10**18)
    b=odds.query((dic[a]+1)//2,r//2)
    odds.update(dic[b]//2,10**18)
    ans.append(a)
    ans.append(b)
    tl=dic[a]
    tr=dic[b]
    if tl!=l:
      heapq.heappush(q,(evens.query(l//2,(tl-1)//2),l,tl-1))
    if tl+1<tr-1:
      heapq.heappush(q,(odds.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if tr!=r:
      heapq.heappush(q,(evens.query((tr+1)//2,r//2),tr+1,r))
print(*ans)

N = int(input())
*P, = map(int,input().split())
M = [0]*(N+1)
from heapq import heappush,heappop
for i,p in enumerate(P):
    M[p] = i

INF = 10**9

def init(P,n):
    n0 = 2**(n-1).bit_length()
    data = [INF]*(n0*2)
    data[n0-1:n0+n-1] = P
    for i in range(n0-2,-1,-1):
        data[i] = min(data[2*i+1],data[2*i+2])
    return data

def get_data(data,l,r):
    n0 = len(data)//2
    l += n0
    r += n0
    while l<r:
        if r&1:
            r-=1
            yield data[r-1]
        if l&1:
            yield data[l-1]
            l += 1
        l>>=1
        r>>=1

def get(data,l,r):
    return min(get_data(data,l,r))

d0 = init(P[0::2],N//2)
d1 = init(P[1::2],N//2)


def query_x(l, r):
    if l % 2 == 0:
        x = get(d0, l//2, r//2)
    else:
        x = get(d1, l//2, r//2)
    return x
def query_y(l, r):
    if l % 2 == 0:
        y = get(d1, l//2, r//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y


que = [(query_x(0,N),0,N)]
ans = []
while que:
    x, l, r = heappop(que)
    if l+2 < r:
        xi = M[x]
        y = query_y(xi, r)
        yi = M[y]
 
        # [l, xi)
        if l < xi:
            heappush(que, (query_x(l, xi), l, xi))
        # [xi+1, yi)
        if xi+1 < yi:
            heappush(que, (query_x(xi+1, yi), xi+1, yi))
        # [yi+1, r)
        if yi+1 < r:
            heappush(que, (query_x(yi+1, r), yi+1, r))
    else:
        y = P[r-1]
    ans.append("%d %d" % (x, y))
print(*ans)

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

N = int(input())
A = [int(x) for x in input().split()]
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append([x if x < y else y for x,y in zip(sp[-1][:-L], sp[-1][L:])])

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))

import sys
input = sys.stdin.readline
import numpy as np
from heapq import heappush, heappop

N = int(input())
A = np.array(input().split(), dtype=np.int32)
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append(np.minimum(sp[-1][:-L], sp[-1][L:]))

def RMQ(x,y):
    if (y-x)&1: 
        y -= 1
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    return min(sp[n-1][x], sp[n-1][y+2-(1<<(n-1))])

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    if x != None:
        answer.append(x)
        answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer)))

import sys
input = sys.stdin.readline
from heapq import heappush, heappop

N = int(input())
A = [int(x) for x in input().split()]
a_to_i = {a:i for i,a in enumerate(A)}

# sparse table を使ってRMQ
# parityの同じところだけを見るようにしておく

U = len(A).bit_length()
sp = [None,A]
for i in range(2,U):
    L = 1 << (i-1)
    sp.append([x if x < y else y for x,y in zip(sp[-1][:-L], sp[-1][L:])])

def RMQ(x,y):
    # x番目から偶数番目だけ見て[x,y]での最小値を返す
    d = y - x
    if d <= 1:
        return A[x]
    n = d.bit_length()
    arr = sp[n-1]
    ax = arr[x]
    ay = arr[y+2-(1<<(n-1))]
    return ax if ax < ay else ay

def F(x,y):
    # 辞書式で最小の2つ組をとる
    # そのあと、今後調べないといけない区間の一覧を返す
    x1 = RMQ(x,y-1)
    i1 = a_to_i[x1]
    x2 = RMQ(i1+1,y)
    i2 = a_to_i[x2]
    task = ((x,y) for x,y in ((x,i1-1), (i1+1,i2-1), (i2+1,y)) if y > x)
    return x1,x2,task

q = [(None,None,((0,N-1),))]
answer = []
while q:
    x,y,task = heappop(q)
    answer.append(x)
    answer.append(y)
    for left,right in task:
        heappush(q,F(left,right))

print(' '.join(map(str,answer[2:])))

class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    P = list(map(int,input().split()))
    Even = []
    Odd = []
    D = {}
    for i in range(N//2):
        e = P[2*i]
        o = P[2*i+1]
        D[e] = i
        D[o] = i
        Even.append(e)
        Odd.append(o)
    
    E_Seg = SegTree(Even,float("inf"),min)
    O_Seg = SegTree(Odd,float("inf"),min)
    
    import heapq
    heap = []
    # heapq.heappush(heap, item)
    # heapq.heappop(heap)
    
    def BFS(H):
        L = H[0]
        R = H[1]
        if R <= L:
            return -1,-1,-1,-1,-1
        if L%2==0:
            l = L//2
            r = R//2
            mini = E_Seg.query(l,r+1)
            d_mini = D[mini]
            mini_b = O_Seg.query(d_mini, r+1)
            d_mini_b = D[mini_b]
            
            leftH = (L, 2*d_mini-1)
            centH = (2*d_mini+1, 2*d_mini_b)
            rightH = (2*d_mini_b+2, R)
            return mini, mini_b, leftH, centH, rightH
        else:
            l = L//2
            r = R//2
            mini = O_Seg.query(l, r)
            d_mini = D[mini]
            mini_b = E_Seg.query(d_mini+1, r+1)
            d_mini_b = D[mini_b]
            
            leftH = (L, 2*d_mini)
            centH = (2*d_mini+2, 2*d_mini_b-1)
            rightH = (2*d_mini_b+1, R)
            return mini, mini_b, leftH, centH, rightH
        
    H = (0, N-1)
    m1,m2,LH,CH,RH = BFS(H)
    #print(m1,m2)
    heapq.heappush(heap, [m1,m2,LH,CH,RH])
    Q = []
    while heap != []:
        m1,m2,LH,CH,RH = heapq.heappop(heap)
        Q += [m1,m2]
        
        m1L,m2L,LHL,CHL,RHL = BFS(LH)
        if m1L != -1:
            heapq.heappush(heap, [m1L,m2L,LHL,CHL,RHL])
        
        m1C,m2C,LHC,CHC,RHC = BFS(CH)
        if m1C != -1:
            heapq.heappush(heap, [m1C,m2C,LHC,CHC,RHC])
        
        m1R,m2R,LHR,CHR,RHR = BFS(RH)
        if m1R != -1:
            heapq.heappush(heap, [m1R,m2R,LHR,CHR,RHR])
    print(*Q)
    
    
    
    
main()

from collections import deque
import heapq
import sys
input = sys.stdin.readline


class SparseTable():
    """区間取得クエリをO(1)で答えるデータ構造をO(NlogN)で構築する
    query(l, r): 区間[l, r)に対するクエリに答える
    """
    def __init__(self, array, n):
        n = len(array)
        self.row_size = n.bit_length()

        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1

        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
                self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                            self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        """クエリの内容"""
        return min(num1, num2)

    def query(self, l, r):
        """区間[l, r)に対するクエリに答える"""
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])


n = int(input())
p = list(map(int, input().split()))

q = [[0] * (n // 2) for i in range(2)]

for i in range(n):
    q[i%2][i//2] = p[i]

ind = {}
for i in range(n):
    ind[p[i]] = i

sp0 = SparseTable(q[0], n // 2)
sp1 = SparseTable(q[1], n // 2)

con = {}
ans = {}
div = 10**6
def solve(l, r):
    q = deque([l * div + r])
    while q:
        pos = q.pop()
        l, r = pos // div, pos % div 
        # min1 = min(q[l%2][l//2:r//2])
        if l % 2 == 0:
            min1 = sp0.query(l//2, r//2)
        else:
            min1 = sp1.query(l//2, r//2)
        use_pos1 = ind[min1]
        
        # min2 = min(q[(l+1)%2][(use_pos1+1)//2:(r+1)//2])
        if (l + 1) % 2 == 0:
            min2 = sp0.query((use_pos1 + 1) // 2, (r + 1) // 2)
        else:
            min2 = sp1.query((use_pos1 + 1) // 2, (r + 1) // 2)
        use_pos2 =  ind[min2]
        
        ans[pos] = min1 * div + min2
        con[pos] = []
        if l != use_pos1:
            con[pos].append(l * div + use_pos1)
            q.append(l * div + use_pos1)
        if use_pos1 + 1 != use_pos2:
            con[pos].append((use_pos1 + 1) * div + use_pos2)
            q.append((use_pos1 + 1) * div + use_pos2)
        if use_pos2 + 1 != r:
            con[pos].append((use_pos2 + 1) * div + r)
            q.append((use_pos2 + 1) * div + r)

    return


solve(0, n)
res = []
q = [(ans[n], n)]
while q:
    num, i = heapq.heappop(q)
    min1, min2 = num // div, num % div
    res.append(min1)
    res.append(min2)
    for new_num in con[i]:
        heapq.heappush(q, (ans[new_num], new_num))
print(*res)

from heapq import heappop, heappush
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
p = [int(x) for x in input().split()]


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:]

    def update(self, k, x):
        k += self.N-1
        self.tree[k] = x
        while k+1:
            k = (k-1)//2
            self.tree[k] = self.opr(self.tree[k*2+1], self.tree[k*2+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            return
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 1:
            if p & 1 == 0:
                res = self.opr(res, self.tree[p])
            if q & 1 == 1:
                res = self.opr(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.opr(res, self.tree[p])
        else:
            res = self.opr(self.opr(res, self.tree[p]), self.tree[q])
        return res


ind = [0]*(n+1)
Odd = SegmentTree([10**30]*n)
Even = SegmentTree([10**30]*n)

for i in range(n):
    ind[p[i]] = i
    if i % 2 == 0:
        Even.update(i, p[i])
    else:
        Odd.update(i, p[i])

cand = []
heappush(cand, (Even.query(0, n), 0, n, True))

q = []
while len(q) < n:
    first, l, r, is_even = heappop(cand)
    if is_even:
        second = Odd.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Even.query(l, ind[first]), l, ind[first], True))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Odd.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], False))
        if ind[second]+1 < r:
            heappush(
                cand, (Even.query(ind[second], r), ind[second]+1, r, True))
    else:
        second = Even.query(ind[first]+1, r)
        q.extend([first, second])
        if l < ind[first]:
            heappush(cand, (Odd.query(l, ind[first]), l, ind[first], False))
        if ind[first] + 1 < ind[second]:
            heappush(
                cand, (Even.query(ind[first]+1, ind[second]), ind[first]+1, ind[second], True))
        if ind[second]+1 < r:
            heappush(
                cand, (Odd.query(ind[second], r), ind[second]+1, r, False))

print((*q))


from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# lから1つおきにみたときの最小値を求める特別製
class SparseTable:
    def __init__(self, aa):
        inf = 10 ** 16
        w = len(aa)
        h = w.bit_length()
        table = [aa] * 2 + [[inf] * w for _ in range(h - 2)]
        tablei1 = table[0]
        for i in range(2, h):
            tablei = table[i]
            shift = 1 << (i - 1)
            for j in range(w):
                rj = j + shift
                if rj >= w: break
                tablei[j] = min(tablei1[j], tablei1[rj])
            tablei1 = tablei
        self.table = table

    # [l,r)の最小値
    def min(self, l, r):
        if (r - l) % 2: r += 1
        i = (r - l).bit_length() - 1
        tablei = self.table[i]
        Lmin = tablei[l]
        Rmin = tablei[r - (1 << i)]
        if Lmin < Rmin: Rmin = Lmin
        return Rmin

def main():
    n = int(input())
    pp = LI()
    st = SparseTable(pp)
    ptoi = [0] + [i for i, p in sorted(enumerate(pp), key=lambda x: x[1])]
    # 区間偶数番目の最小値と[l,r)をヒープに
    hp = []
    heappush(hp, [st.min(0, n), 0, n])
    ans = []
    for _ in range(n // 2):
        x, l, r = heappop(hp)
        if l + 2 == r:
            ans += [pp[l], pp[l + 1]]
            continue
        xi = ptoi[x]
        y = st.min(xi + 1, r)
        yi = ptoi[y]
        if xi > l:
            heappush(hp, [st.min(l, xi), l, xi])
        if xi + 1 < yi:
            heappush(hp, [st.min(xi + 1, yi), xi + 1, yi])
        if yi < r - 1:
            heappush(hp, [st.min(yi + 1, r), yi + 1, r])
        ans += [x, y]
    print(*ans)

main()


from heapq import heappop, heappush
INF = 10**30

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L < R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])			
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
a = list(map(int, input().split()))

even, odd = Rmin(n), Rmin(n)
for i in range(n):
	if i%2 == 0:
		even.Update(i, a[i]*(10**7) + i)
	else:
		odd.Update(i, a[i]*(10**7) + i)

d = dict()

def search(l, r):
	if l%2 == 0:
		p = even.Get(l, r+1)
		q = odd.Get(p%(10**7)+1, r+1)
	else:
		p = odd.Get(l, r+1)
		q = even.Get(p%(10**7)+1, r+1)
	return p, q

x, y = search(0, n-1)
d[x%(10**7)] = (y, 0, n-1)
que = [x]
ans = []

while que:
	x = heappop(que)
	y, l, r = d[x%(10**7)]
	ans += [x//(10**7), y//(10**7)]

	if l != x%(10**7):
		p, q = search(l, x%(10**7)-1)
		d[p%(10**7)] = (q, l, x%(10**7)-1)
		heappush(que, p)

	if r != y%(10**7):
		p, q = search(y%(10**7)+1, r)
		d[p%(10**7)] = (q, y%(10**7)+1, r)
		heappush(que, p)

	if x%(10**7)+1 != y%(10**7):
		p, q = search(x%(10**7)+1, y%(10**7)-1)
		d[p%(10**7)] = (q, x%(10**7)+1, y%(10**7)-1)
		heappush(que, p)

print(*ans)