Problem:
 Score : 800 points    Problem Statement 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 1 4
3 2 4 1      Sample Output 1 3 1 2 4  The solution above is obtained as follows:     p  q      (3, 2, 4, 1)  ()    ↓  ↓    (3, 1)  (2, 4)    ↓  ↓    ()  (3, 1, 2, 4)          Sample Input 2 2
1 2      Sample Output 2 1 2       Sample Input 3 8
4 6 3 2 8 5 7 1      Sample Output 3 3 1 2 7 4 6 8 5  The solution above is obtained as follows:     p  q      (4, 6, 3, 2, 8, 5, 7, 1)  ()    ↓  ↓    (4, 6, 3, 2, 7, 1)  (8, 5)    ↓  ↓    (3, 2, 7, 1)  (4, 6, 8, 5)    ↓  ↓    (3, 1)  (2, 7, 4, 6, 8, 5)    ↓  ↓    ()  (3, 1, 2, 7, 4, 6, 8, 5)

Solution (Python):
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)

        
        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)

        
        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)

    
    
    
    
    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)))

Solution (Python):
class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): 
        return self.dat[k+self.N0]



import sys
read = sys.stdin.read
readline = sys.stdin.readline
sys.setrecursionlimit(10**5)

n,*p = map(int,read().split())

INF = 1<<30
p += [INF,INF]

def argmin(i,j):
    if p[i] < p[j]: return i
    else: return j

even = segment_tree(n//2+1,argmin,n)
odd = segment_tree(n//2+1,argmin,n+1)

even.build(range(0,n+2,2))
odd.build(range(1,n+2,2))

ans = [0]*n

def get(i,j):
    return odd.query(i//2,(j-1)//2)  if i%2 else even.query(i//2,(j-1)//2)

from heapq import *
k = get(0,n-1)
q = [(p[k],k,0,n-1)]

for I in range(n//2):
    v,k,i,j = heappop(q)
    l = even.query((k+1)//2,j//2) if i%2 else odd.query((k+1)//2,j//2)
    
    
        
    ans[2*I] = v
    ans[2*I+1] = p[l]
    
    if i < k+1:
        kk = get(i,k-1)
        heappush(q,(p[kk],kk,i,k-1))
    if k+1<l-1:
        kk = get(k+1,l-1)
        heappush(q,(p[kk],kk,k+1,l-1))
    if l+1 < j:
        kk = get(l+1,j)
        heappush(q,(p[kk],kk,l+1,j))
    
print(*ans)

Solution (Python):
from sys import stdin
import heapq

def make_ST(n,first): 

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): 

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = min(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): 

    if r <= a or b <= l: 
        return (float("inf"),float("inf"))
    
    if a <= l and r <= b: 
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return min(c1,c2)
        

def want(L,R):

    if L >= R:
        return
    elif L + 1 == R:
        heapq.heappush( q, (p[L],p[R],float("inf"),float("-inf"),float("inf"),float("-inf")) )
        return

    if L % 2 == 0:
        nx,xind = RMQ_query(L,R+1,0,0,(len(emin)+1)//2,emin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(omin)+1)//2,omin)
    else:
        nx,xind = RMQ_query(L,R+1,0,0,(len(omin)+1)//2,omin)
        ny,yind = RMQ_query(xind+1,R+1,0,0,(len(emin)+1)//2,emin)

    

    heapq.heappush( q , (nx,ny,xind,yind,L,R) )
    return

N = int(input())
p = list(map(int, stdin.readline().split()))


omin = make_ST(N, (float("inf") , float("inf")) )
emin = make_ST(N, (float("inf") , float("inf")) )

for i in range(N):
    if i % 2 == 0:
        RMQ_update_point( (p[i],i) ,i,emin)
    else:
        RMQ_update_point( (p[i],i) ,i,omin)

q = []
want(0,N-1)
ans = []

while len(q) > 0:

    x,y,xi,yi,NL,NR = heapq.heappop(q)
    ans.append(x)
    ans.append(y)

    want(NL,xi-1)
    want(xi+1,yi-1)
    want(yi+1,NR)

print (*ans)

Solution (Python):
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:  
    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):  
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        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)

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


class SegmentTree:  
    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):  
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        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)

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


class SegmentTree:  
    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):  
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        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)

Solution (Python):
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)

Solution (Python):
def main():
    n = int(input())
    p = list(map(lambda x: int(x)-1, 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 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()

Solution (Python):
import sys
from heapq import heappop, heappush


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_array(cls, arr, INF):
        ins = cls(len(arr), INF)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = min(ins.tree[l], ins.tree[r])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *ppp = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18
indices = [0] * (n + 1)
even_p = [INF] * n
odd_p = [INF] * n
for i, p in enumerate(ppp):
    indices[p] = i
    if i % 2 == 0:
        even_p[i] = p
    else:
        odd_p[i] = p

sgt0 = SegTreeMin.from_array(even_p, INF)
sgt1 = SegTreeMin.from_array(odd_p, INF)
sgt = [sgt0, sgt1]
ans = []
heap = []
data = {}
first_p = sgt0.get_min(0, n)
i = indices[first_p]
first_q = sgt1.get_min(i, n)
j = indices[first_q]
heap.append(first_p)
data[first_p] = (first_q, 0, n, i, j)
while heap:
    p = heappop(heap)
    q, l, r, i, j = data.pop(p)
    ans.append(p)
    ans.append(q)
    if l < i:
        k = l % 2
        np = sgt[k].get_min(l, i)
        ni = indices[np]
        nq = sgt[k ^ 1].get_min(ni, i)
        nj = indices[nq]
        heappush(heap, np)
        data[np] = (nq, l, i, ni, nj)
    if i + 1 < j:
        k = (i + 1) % 2
        np = sgt[k].get_min(i + 1, j)
        ni = indices[np]
        nq = sgt[k ^ 1].get_min(ni, j)
        nj = indices[nq]
        heappush(heap, np)
        data[np] = (nq, i + 1, j, ni, nj)
    if j + 1 < r:
        k = (j + 1) % 2
        np = sgt[k].get_min(j + 1, r)
        ni = indices[np]
        nq = sgt[k ^ 1].get_min(ni, r)
        nj = indices[nq]
        heappush(heap, np)
        data[np] = (nq, j + 1, r, ni, nj)

print(*ans)

Solution (Python):
import sys
from heapq import heappop, heappush


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_array(cls, arr, INF):
        ins = cls(len(arr), INF)
        ins.tree[ins.offset:ins.offset + len(arr)] = arr
        for i in range(ins.offset - 1, 0, -1):
            l = i << 1
            r = l + 1
            ins.tree[i] = min(ins.tree[l], ins.tree[r])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, *ppp = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18

sgt0 = SegTreeMin.from_array([(p if i % 2 == 0 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt1 = SegTreeMin.from_array([(p if i % 2 == 1 else INF, i) for i, p in enumerate(ppp)], (INF, -1))
sgt = [sgt0, sgt1]
ans = []
heap = []
first_p, i = sgt0.get_min(0, n)
first_q, j = sgt1.get_min(i, n)
heap.append((first_p, first_q, 0, n, i, j))
while heap:
    p, q, l, r, i, j = heappop(heap)
    ans.append(p)
    ans.append(q)
    if l < i:
        k = l % 2
        np, ni = sgt[k].get_min(l, i)
        nq, nj = sgt[k ^ 1].get_min(ni, i)
        heappush(heap, (np, nq, l, i, ni, nj))
    if i + 1 < j:
        k = (i + 1) % 2
        np, ni = sgt[k].get_min(i + 1, j)
        nq, nj = sgt[k ^ 1].get_min(ni, j)
        heappush(heap, (np, nq, i + 1, j, ni, nj))
    if j + 1 < r:
        k = (j + 1) % 2
        np, ni = sgt[k].get_min(j + 1, r)
        nq, nj = sgt[k ^ 1].get_min(ni, r)
        heappush(heap, (np, nq, j + 1, r, ni, nj))

print(*ans)

Solution (Python):

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



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)