Buggy python submission (verdict: Time Limit Exceeded):
"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""
from sys import stdin
import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

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

N = int(stdin.readline())
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)



Fixed submission:
from sys import stdin
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)

Buggy python submission (verdict: Time Limit Exceeded):
"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""
from sys import stdin
import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)



Fixed submission:
from sys import stdin
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)

Buggy python submission (verdict: Time Limit Exceeded):

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""

import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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

    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)

    #print (L,R,xind,yind)

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

N = int(input())
p = list(map(int,input().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 = [0]*N
ind=0

for i in range(N//2):

    x,y,xi,yi,NL,NR = heapq.heappop(q)
    ans[ind] = x
    ans[ind+1] = y
    ind += 2

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

print (*ans)


Fixed submission:
from sys import stdin
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)

Buggy python submission (verdict: Time Limit Exceeded):

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""

import sys
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

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

N = int(input())
p = list(map(int,input().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)


Fixed submission:
from sys import stdin
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)

Buggy python submission (verdict: Time Limit Exceeded):

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

======ちょっと答えを見た======

マージ部分がやばい？
親が選択されるまで子は選択できない
優先度付きキューで管理か
親を処理した時点で子を優先度付きキューに入れるのか

(左値,右値,左index,右index,L,R)を入れればいいか

"""

import sys
import heapq
sys.setrecursionlimit(200001)

#RMQ用のSparseTableを作成
import math
def make_SparseTable(lis):

    spt_len = 0
    while spt_len ** 2 <= len(lis):
        spt_len += 1
    spt_len += 5

    N = len(lis)
    ret = [[float("inf")] * spt_len for i in range(N)]

    for i in range(N):
        ret[i][0] = lis[i]
    
    for j in range(spt_len-1):
        j += 1

        for i in range(N):

            if i + 2**(j-1) < N:
                ret[i][j] = min(ret[i][j-1] , ret[i+2**(j-1)][j-1])
            else:
                ret[i][j] = ret[i][j-1]

    return ret

#[a,b]の最小値を求める
def RMQ_SPT(a,b,spt):

    
    if a == b:
        return (p[a],a)
    
    qlen = b-a+1
    ind = int(math.log(qlen,2))

    #print (a,b,ind,b-2**ind+1)

    return min(spt[a][ind] , spt[b-2**ind+1][ind])

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_SPT(L,R,emin)
        ny,yind = RMQ_SPT(xind+1,R,omin)
    else:
        nx,xind = RMQ_SPT(L,R,omin)
        ny,yind = RMQ_SPT(xind+1,R,emin)

    #print (L,R,xind,yind)

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

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


ominL = []
eminL = []
for i in range(N):
    if i % 2 == 0:
        ominL.append( (float("inf"),i) )
        eminL.append( ( p[i] , i ) )
    else:
        eminL.append( (float("inf"),i) )
        ominL.append( ( p[i] , i ) )

emin = make_SparseTable(eminL)
omin = make_SparseTable(ominL)

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)


Fixed submission:
from sys import stdin
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)

Buggy python submission (verdict: Time Limit Exceeded):

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

"""

import sys
sys.setrecursionlimit(200001)

#RMQ用のSparseTableを作成
import math
def make_SparseTable(lis):

    spt_len = 0
    while spt_len ** 2 <= len(lis):
        spt_len += 1
    spt_len += 5

    N = len(lis)
    ret = [[float("inf")] * spt_len for i in range(N)]

    for i in range(N):
        ret[i][0] = lis[i]
    
    for j in range(spt_len-1):
        j += 1

        for i in range(N):

            if i + 2**(j-1) < N:
                ret[i][j] = min(ret[i][j-1] , ret[i+2**(j-1)][j-1])
            else:
                ret[i][j] = ret[i][j-1]

    return ret

#[a,b]の最小値を求める
def RMQ_SPT(a,b,spt):

    
    if a == b:
        return (p[a],a)
    
    qlen = b-a+1
    ind = int(math.log(qlen,2))

    #print (a,b,ind,b-2**ind+1)

    return min(spt[a][ind] , spt[b-2**ind+1][ind])

def want(L,R):

    if L >= R:
        return [(float("inf"),float("inf"))]
    elif L + 1 == R:
        return [(p[L],p[R]),(float("inf"),float("inf"))]

    ret = []
    add = []

    if L % 2 == 0:
        nx,xind = RMQ_SPT(L,R,emin)
        ny,yind = RMQ_SPT(xind+1,R,omin)
        ret.append( (nx,ny) )
    else:
        nx,xind = RMQ_SPT(L,R,omin)
        ny,yind = RMQ_SPT(xind+1,R,emin)
        ret.append( (nx,ny) )

    #print (L,R,xind,yind)

    LL = want(L,xind-1)
    MM = want(xind+1,yind-1)
    RR = want(yind+1,R)
        
    li = 0
    mi = 0
    ri = 0

    for i in range(len(LL)+len(MM)+len(RR)-3):
        nmin = min(LL[li] , MM[mi] , RR[ri])
        if nmin == LL[li]:
            ret.append(LL[li])
            li += 1
        elif nmin == MM[mi]:
            ret.append(MM[mi])
            mi += 1
        else:
            ret.append(RR[ri])
            ri += 1

    ret.append( (float("inf") , float("inf")) )
    return ret

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


ominL = []
eminL = []
for i in range(N):
    if i % 2 == 0:
        ominL.append( (float("inf"),i) )
        eminL.append( ( p[i] , i ) )
    else:
        eminL.append( (float("inf"),i) )
        ominL.append( ( p[i] , i ) )

emin = make_SparseTable(eminL)
omin = make_SparseTable(ominL)

#print (emin)

ans = want(0,N-1)
alis = []
for i in range(N//2):
    alis.append(ans[i][0])
    alis.append(ans[i][1])
print (*alis)


Fixed submission:
from sys import stdin
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)

Buggy python submission (verdict: Time Limit Exceeded):

"""

https://atcoder.jp/contests/arc080/tasks/arc080_c

まず、辞書順最小なので一番左にできる要素はどれか考える

ABCD
→可能なのは A,C

→偶数番目だけ？(0 indexedで)
→右に奇数個・左に偶数個ある場合しか先頭にはなれないので正しそう

次に、2番目になる要素はどれか？
→一番目より左は確定
→奇数個並んでる場合、最後に残せるやつ
ABCDEだと
→A,C,E なので奇数番目だけ

3番目の要素は？
→偶数番目から自由に選べる
4番目は？
→最後に選んだ偶数番目から右に探索して、探索済みが出てくるまでに当たる奇数番目のうち最小

あとは高速化だ！

分割統治
偶奇分けて最小と最大2つのRMQを出せるようにしとく
→めんどすぎ！！！

偶数番目と奇数番目・最小で2つのセグ木
偶数番目から最小を選ぶ(X)
→それより右の奇数番目から最小を選ぶ(Y)
その左側、真ん中、右側を分けておなじことをする

(X,Y),3つの部分を小さいほうからどん欲にとってマージした奴
をreturnする

SPTを使えば早いか
maxは-1をかけて出せばいいや

"""

import sys
sys.setrecursionlimit(200001)

#RMQ用のSparseTableを作成
import math
def make_SparseTable(lis):

    spt_len = 0
    while spt_len ** 2 <= len(lis):
        spt_len += 1
    spt_len += 5

    N = len(lis)
    ret = [[float("inf")] * spt_len for i in range(N)]

    for i in range(N):
        ret[i][0] = lis[i]
    
    for j in range(spt_len-1):
        j += 1

        for i in range(N):

            if i + 2**(j-1) < N:
                ret[i][j] = min(ret[i][j-1] , ret[i+2**(j-1)][j-1])
            else:
                ret[i][j] = ret[i][j-1]

    return ret

#[a,b]の最小値を求める
def RMQ_SPT(a,b,spt):

    
    if a == b:
        return (p[a],a)
    
    qlen = b-a+1
    ind = int(math.log(qlen,2))

    #print (a,b,ind,b-2**ind+1)

    return min(spt[a][ind] , spt[b-2**ind+1][ind])

def want(L,R):

    if L >= R:
        return [(float("inf"),float("inf"))]
    elif L + 1 == R:
        return [(p[L],p[R]),(float("inf"),float("inf"))]

    ret = []
    add = []

    if L % 2 == 0:
        nx,xind = RMQ_SPT(L,R,emin)
        ny,yind = RMQ_SPT(xind+1,R,omin)
        ret.append( (nx,ny) )
    else:
        nx,xind = RMQ_SPT(L,R,omin)
        ny,yind = RMQ_SPT(xind+1,R,emin)
        ret.append( (nx,ny) )

    #print (L,R,xind,yind)

    LL = want(L,xind-1)
    MM = want(xind+1,yind-1)
    RR = want(yind+1,R)
        
    li = 0
    mi = 0
    ri = 0

    for i in range(len(LL)+len(MM)+len(RR)-3):
        nmin = min(LL[li] , MM[mi] , RR[ri])
        if nmin == LL[li]:
            ret.append(LL[li])
            li += 1
        elif nmin == MM[mi]:
            ret.append(MM[mi])
            mi += 1
        else:
            ret.append(RR[ri])
            ri += 1

    ret.append( (float("inf") , float("inf")) )
    return ret

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


ominL = []
eminL = []
for i in range(N):
    if i % 2 == 0:
        ominL.append( (float("inf"),i) )
        eminL.append( ( p[i] , i ) )
    else:
        eminL.append( (float("inf"),i) )
        ominL.append( ( p[i] , i ) )

emin = make_SparseTable(eminL)
omin = make_SparseTable(ominL)

#print (emin)

ans = want(0,N-1)
alis = []
for i in range(N//2):
    alis.append(ans[i][0])
    alis.append(ans[i][1])
print (*alis)


Fixed submission:
from sys import stdin
import heapq

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    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): #葉のindex(0-origin)がpointの要素をnumにする/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): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        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)

    #print (L,R,xind,yind)

    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)