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)



Sample input:
4
3 2 4 1


Sample output:
3 1 2 4

Submission status: Wrong Answer

Solution code:
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,(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,(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])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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//2-1),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-1)-l>0:
      heapq.heappush(q,(odds.query(l,(tl-1)//2),l,tl-1))
    if (tr-1)-(tl+1)>0:
      heapq.heappush(q,(evens.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if r-(tr+1)>0:
      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-1)-l>0:
      heapq.heappush(q,(evens.query(l,(tl-1)//2),l,tl-1))
    if (tr-1)-(tl+1)>0:
      heapq.heappush(q,(odds.query((tl+1)//2,(tr-1)//2),tl+1,tr-1))
    if r-(tr+1)>0:
      heapq.heappush(q,(evens.query((tr+1)//2,r//2),tr+1,r))
print(*ans)

Submission status: Wrong Answer

Solution code:
#####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,l,r=first(l,index)
    if val!=-1:
        heapq.heappush(que,((val,val2),l,index))
    val,val2,l,r=first(index+1,index2)
    if val!=-1:
        heapq.heappush(que,((val,val2),index+1,index2))
    val,val2,l,r=first(index2+1,r)
    if val!=-1:
        heapq.heappush(que,((val,val2),index2+1,r))

print(*ans)

Submission status: Wrong Answer

Solution code:
class SegmentTree:#抽象セグ木
    def __init__(self, N, id, fun):#id:単位元
        self.N0 = 2**(N-1).bit_length()
        self.id = id
        self.data = [(self.id, i) for i in range(2*self.N0)]
        self.fun = fun
    def update(self, k, x):
        k+=self.N0-1
        self.data[k] = (x, k-self.N0+1)
        while k>=0:
            k = (k-1)//2
            self.data[k] = self.fun(self.data[2*k+1], self.data[2*k+2])
    def query(self, l, r):#[l, r)
        L = l+self.N0; R = r+self.N0
        s = (self.id, self.id)
        while L<R:
            if R&1:
                R-=1
                s = self.fun(s, self.data[R-1])
            if L&1:
                s = self.fun(s, self.data[L-1])
                L+=1
            L >>= 1; R>>=1
        return s
inf = 10**18
N = int(input())
p = list(map(int, input().split()))
S1 = SegmentTree(N//2, inf, min)
S2 = SegmentTree(N//2, inf, min)
que = [(0, 0, N)]
res = []
for i, x in enumerate(p[::2]):
    S1.update(i, x)
for i, x in enumerate(p[1::2]):
    S2.update(i, x)
while que:
    k, l, r = que.pop()
    if l>=r:
        continue
    if r-l == 2:
        res.append((k+1, p[l], p[l+1]))
        continue
    if l%2 == 0:
        x, i = S1.query(l//2, r//2)
        i*=2
        que.append((k+1, l, i))
        y, j = S2.query(i//2, r//2)
        j = j*2+1
        res.append((k+1, x, y))
        que.append((k+1, i+1, j))
        que.append((k+1, j+1, r))
    else:
        x, i = S2.query(l//2, r//2)
        i=2*i+1
        que.append((k+1, l, i))
        y, j = S1.query(i//2+1, r//2+1)
        j = j*2
        res.append((k+1, x, y))
        que.append((k+1, i+1, j))
        que.append((k+1, j+1, r))
res.sort()
ans = []
for a, b, c in res:
    ans.append(b)
    ans.append(c)
print(*ans)

Submission status: Wrong Answer

Solution code:
# 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, l, r):
    if l+1 == r:
        return P[l]
    if l+2 == r:
        return min(P[l], P[l+1])
    if l+3 == r:
        return min(P[l], P[l+1], P[l+2])
    if l+4 == r:
        return min(P[l], P[l+1], P[l+2], P[l+3])
    return __get(data, l, r, 0, 0, len(data)//2)

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)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int, input().split()))
PE = []
PO = []

for n in range(0, N - 1, 2):
    PE.append(P[n])
    PO.append(P[n + 1])

PE.sort()
PO.sort()

res = ""

while PO:
    res += str(PE.pop(0)) + " "
    res += str(PO.pop(0)) + " "

print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# coding: utf-8

# AtCoder Regular Contest 080
# Problem E: Young Maids

import sys

def solve(p):
  N = len(p)
  if N == 0: return []
  if N == 2: return [tuple(p)]

  # 偶数位置の数のうち最小のものの位置
  left  = min([(p[i], i) for i in range(N) if i % 2 == 0])[1]
  # left以降の奇数位置の数のうち最小のものの位置
  right = min([(p[i], i) for i in range(left + 1, N) if i % 2 != 0])[1]

  # (left, right)の対を最後に消すのが最適
  head = (p[left], p[right])

  # 残りを3区間に分け, それぞれ最適解を求める
  pre  = solve(p[: left])
  mid  = solve(p[left + 1 : right])
  post = solve(p[right + 1 :])

  # 連結して整列
  segs = pre + mid + post
  segs.sort()

  return [head] + segs

# 対のリストを平坦化
def flatten(l):
  return [x for p in l for x in list(p)]

def splitIntoNums(line):
  words = line.strip().split()
  return [int(w) for w in words]

while True:
  l1 = sys.stdin.readline()
  l2 = sys.stdin.readline()
  if not l1: break
  N, = splitIntoNums(l1)
  p  = splitIntoNums(l2)
  if len(p) != N: raise
  print(' '.join(map(str, flatten(solve(p)))))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    p = ILI()
    return N, p


def solve(N, p):
    num_ind = [-1] * (N + 1)
    for ind, _p in enumerate(p):
        num_ind[_p] = ind

    ans_pair = []
    count = 0
    while count != N:
        for i in range(1, N + 1):
            if num_ind[i] == -1:
                continue
            else:
                first_ind = num_ind[i]
                num_f = i
                num_ind[i] = -1
                for j in range(i + 1, N + 1):
                    if num_ind[j] == -1:
                        continue
                    else:
                        next_ind = num_ind[j]
                        if first_ind % 2 == 1:
                            if next_ind < first_ind and (first_ind - next_ind) % 2 == 1:
                                num_n = j
                                num_ind[j] = -1
                                break
                            else:
                                continue
                        else:
                            if first_ind < next_ind and (next_ind - first_ind) % 2 == 1:
                                num_n = j
                                num_ind[j] = -1
                                break
                            else:
                                continue
                break

        if first_ind > next_ind:
            ans_pair.append("{} {}".format(num_n, num_f))
            for i in range(1, N + 1):
                if next_ind < num_ind[i] < first_ind:
                    num_ind[i] -= 1
                if num_ind[i] > first_ind:
                    num_ind[i] -= 2
        else:
            ans_pair.append("{} {}".format(num_f, num_n))
            for i in range(1, N + 1):
                if first_ind < num_ind[i] < next_ind:
                    num_ind[i] -= 1
                if num_ind[i] > next_ind:
                    num_ind[i] -= 2

        count += 2

    ans = " ".join(ans_pair)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    p = ILI()
    return N, p


def solve(N, p):
    num_ind = [-1] * (N + 1)
    for ind, _p in enumerate(p):
        num_ind[_p] = ind

    ans_pair = []
    count = 0
    while count != N:
        for i in range(1, N + 1):
            if num_ind[i] == -1:
                continue
            else:
                first_ind = num_ind[i]
                num_f = i
                num_ind[i] = -1
                for j in range(i + 1, N + 1):
                    if num_ind[j] == -1:
                        continue
                    else:
                        next_ind = num_ind[j]
                        if first_ind % 2 == 1:
                            if next_ind < first_ind and (first_ind - next_ind) % 2 == 1:
                                num_n = j
                                num_ind[j] = -1
                                break
                            else:
                                continue
                        else:
                            if first_ind < next_ind and (next_ind - first_ind) % 2 == 1:
                                num_n = j
                                num_ind[j] = -1
                                break
                            else:
                                continue
                break

        if first_ind > next_ind:
            ans_pair.append("{} {}".format(num_n, num_f))
            for i in range(1, N + 1):
                if next_ind < num_ind[i] < first_ind:
                    num_ind[i] -= 1
                if num_ind[i] > first_ind:
                    num_ind[i] -= 2
        else:
            ans_pair.append("{} {}".format(num_n, num_f))
            for i in range(1, N + 1):
                if first_ind < num_ind[i] < next_ind:
                    num_ind[i] -= 1
                if num_ind[i] > next_ind:
                    num_ind[i] -= 2

        count += 2

    ans = " ".join(ans_pair)

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
import heapq

def dfs(p, cnt):
    global ans, pq
    n = len(p)
    if n == 0:
        return
    mn1 = 10**6
    mn2 = 10**6
    st = 0
    end = 0
    for i in xrange(0, n, 2):
        if p[i] < mn1:
            mn1 = p[i]
            st = i
    for i in xrange(1, n, 2):
        if p[i] < mn2:
            mn2 = p[i]
            end = i
    heapq.heappush(pq, [cnt, (mn1,mn2)])
    dfs(p[0: st], cnt + 1)
    dfs(p[end + 1: n], cnt + 1)
    dfs(p[st + 1: end], cnt + 1)

n = int(raw_input())
p = map(int, raw_input().split())
ans = []
pq=[]
dfs(p, 0)
ans.sort()
while len(pq) != 0:
    cnt, ans = heapq.heappop(pq)
    print ans[0], ans[1],
print

Submission status: Time Limit Exceeded

Solution code:
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)
    
    # 長さNの配列 initial で初期化
    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])

    # a_k の値を x に更新
    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

    # 区間[L,R]をopでまとめる
    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): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

# coding: utf-8
# Your code here!
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)

#print(p[::2],n//2)
even.build(range(0,n+2,2))
odd.build(range(1,n+2,2))

#print(p)
#print(even.dat)
#print(odd.dat)

"""
def merge(a,b):
    la,lb = len(a),len(b)
    res = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb:
            res[i:] = a[ia:]
            return res
        if ia==la:
            res[i:] = b[ib:]
            return res
        if a[ia][0] <= b[ib][0]:
            res[i] = a[ia]
            ia += 1
        else:
            res[i] = b[ib]
            ib += 1
    return res

def merge3(l0,l1,l2):
    if len(l0) < len(l1):
        if len(l1) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l0,l2),l1)
    else:    
        if len(l0) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l1,l2),l0)
"""

def merge3(a,b,c):
    la,lb,lc = len(a),len(b),len(c)
    res = [0]*(la+lb+lc)
    ia = ib = ic = 0
    for i in range(la+lb+lc):
        idx = -1
        v = 10000000
        if ia!=la: 
            idx = 0
            v = a[ia][0]
        if ib!=lb and b[ib][0] < v: 
            idx = 1
            v = b[ib][0]
        if ic!=lc and c[ic][0] < v: 
            idx = 2
            v = c[ic][0]

        if idx==0:
            res[i] = a[ia]
            ia += 1
        elif idx==1:
            res[i] = b[ib]
            ib += 1
        else:
            res[i] = c[ic]
            ic += 1
    return res


def f(i,j):
    if i >= j: return []
    if i+1==j: return [(p[i],p[j])]

    k = odd.query(i//2,(j-1)//2)  if i%2 else even.query(i//2,(j-1)//2)
    l = even.query((k+1)//2,j//2) if i%2 else odd.query((k+1)//2,j//2)
    res = [(p[k],p[l])] + merge3(f(i,k-1), f(k+1,l-1), f(l+1,j))
    
    #print(f"i={i},j={j},k={k},l={l},{res}")
    
    return res

#print(p)
r = f(0,n-1)

ans = []
for lst in r:
    ans += [lst[0],lst[1]]

print(*ans)



#x = merge3([[1,0],[4,0]],[[2,0]],[[3,0],[6,0]])
#print(x)

Submission status: Time Limit Exceeded

Solution code:
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)
    
    # 長さNの配列 initial で初期化
    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])

    # a_k の値を x に更新
    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

    # 区間[L,R]をopでまとめる
    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): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

# coding: utf-8
# Your code here!
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)

#print(p[::2],n//2)
even.build(range(0,n+2,2))
odd.build(range(1,n+2,2))

#print(p)
#print(even.dat)
#print(odd.dat)

"""
def merge(a,b):
    la,lb = len(a),len(b)
    res = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb:
            res[i:] = a[ia:]
            return res
        if ia==la:
            res[i:] = b[ib:]
            return res
        if a[ia][0] <= b[ib][0]:
            res[i] = a[ia]
            ia += 1
        else:
            res[i] = b[ib]
            ib += 1
    return res

def merge3(l0,l1,l2):
    if len(l0) < len(l1):
        if len(l1) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l0,l2),l1)
    else:    
        if len(l0) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l1,l2),l0)
"""

def merge3(a,b,c):
    la,lb,lc = len(a),len(b),len(c)
    res = [0]*(la+lb+lc)
    ia = ib = ic = 0
    for i in range(la+lb+lc):
        idx = -1
        v = 10000000
        cnt = 0
        if ia!=la: 
            idx = 0
            v = a[ia][0]
            cnt += 1
        if ib!=lb:
            cnt += 1
            if b[ib][0] < v: 
                idx = 1
                v = b[ib][0]
        if ic!=lc:
            cnt += 1
            if c[ic][0] < v: 
                idx = 2
                v = c[ic][0]

        if cnt >= 2:
            if idx==0:
                res[i] = a[ia]
                ia += 1
            elif idx==1:
                res[i] = b[ib]
                ib += 1
            else:
                res[i] = c[ic]
                ic += 1
        else:
            if idx==0:
                res[i:] = a[ia:]
            elif idx==1:
                res[i:] = b[ib:]
            else:
                res[i:] = c[ic:]
            return res            

    return res


def f(i,j):
    if i >= j: return []
    if i+1==j: return [(p[i],p[j])]

    k = odd.query(i//2,(j-1)//2)  if i%2 else even.query(i//2,(j-1)//2)
    l = even.query((k+1)//2,j//2) if i%2 else odd.query((k+1)//2,j//2)
    res = [(p[k],p[l])] + merge3(f(i,k-1), f(k+1,l-1), f(l+1,j))
    
    #print(f"i={i},j={j},k={k},l={l},{res}")
    
    return res

#print(p)
r = f(0,n-1)

ans = []
for lst in r:
    ans += [lst[0],lst[1]]

print(*ans)



#x = merge3([[1,0],[4,0]],[[2,0]],[[3,0],[6,0]])
#print(x)

Submission status: Time Limit Exceeded

Solution code:
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)
    
    # 長さNの配列 initial で初期化
    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])

    # a_k の値を x に更新
    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

    # 区間[L,R]をopでまとめる
    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): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

"""
import random
n = 16
p = list(range(1,n+1))
random.shuffle(p)
print(p)
"""


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)

#print(p[::2],n//2)
even.build(range(0,n+2,2))
odd.build(range(1,n+2,2))

#print(p)
#print(even.dat)
#print(odd.dat)


def merge(a,b):
    la,lb = len(a),len(b)
    res = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb:
            res[i:] = a[ia:]
            return res
        if ia==la:
            res[i:] = b[ib:]
            return res
        if a[ia] <= b[ib]:
            res[i] = a[ia]
            ia += 1
        else:
            res[i] = b[ib]
            ib += 1
    return res

def merge3(l0,l1,l2):
    if len(l0) < len(l1):
        if len(l1) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l0,l2),l1)
    else:    
        if len(l0) < len(l2):
            return merge(merge(l0,l1),l2)
        else:    
            return merge(merge(l1,l2),l0)


def f(i,j):
    if i >= j: return []
    if i+1==j: return [(p[i],p[j])]

    k = odd.query(i//2,(j-1)//2)  if i%2 else even.query(i//2,(j-1)//2)
    l = even.query((k+1)//2,j//2) if i%2 else odd.query((k+1)//2,j//2)
    res = [(p[k],p[l])] + merge3(f(i,k-1), f(k+1,l-1), f(l+1,j))
    
    #print(f"i={i},j={j},k={k},l={l},{res}")
    
    return res

#print(p)
r = f(0,n-1)

ans = []
for lst in r:
    ans += [lst[0],lst[1]]

print(*ans)