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: Time Limit Exceeded

Solution code:
from itertools import count,chain
from collections import deque
import heapq as hq

class MinSegTree:

  def __init__(self, inf, data=None, size=None):
    if data is None and size is None:
      raise Exception('data and size both cannot be None simultaneously')
    self.size = len(data) if size is None else size
    self.depth = (self.size-1).bit_length()
    self.capacity = 1 << self.depth
    self.inf = inf
    if data is None:
      self.data = [self.inf]*(2*self.capacity)
    else:
      self.data = [self.inf]*self.capacity + data + [self.inf]*(self.capacity-len(data))
      for d in reversed(range(self.depth)):
        t = 1 << d
        for i in range(t, 2*t):
          self.data[i] = min(self.data[2*i],self.data[2*i+1])

  def _min_interval(self, a, b):
    result = self.inf
    a += self.capacity
    b += self.capacity
    while a < b:
      if a & 1:
        result = min(result,self.data[a])
        a += 1
      if b & 1:
        b -= 1
        result = min(result,self.data[b])
      a >>= 1
      b >>= 1
    return result

  def _set_val(self, a, val):
    a += self.capacity
    while self.data[a] != val and a > 0:
      self.data[a] = val
      val = min(val,self.data[a^1])
      a >>= 1

  def __getitem__(self, i):
    if isinstance(i, slice):
      return self._min_interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop)
    elif isinstance(i, int):
      return self.data[i+self.capacity]

  def __setitem__(self, i, x):
    self._set_val(i,x)

  def __iter__(self):
    return iter(self.data[self.capacity:])



# from random import shuffle
# N = 2*10**5
# P = list(range(N))
# # shuffle(P)
N = int(input())
P = list(map(int,input().split()))

Te = MinSegTree((N+1,N), list(zip(P[::2], count(0,2))))
To = MinSegTree((N+2,N), list(zip(P[1::2], count(1,2))))


Q = [(Te[0:N//2],0,N)]

ans = []

while Q:
  (p1,i),s,t = hq.heappop(Q)

  T1,T2 = (To,Te) if s&1 else (Te,To)

  p2,j = T2[(i+1)>>1:(t+1)>>1]

  ans += [p1,p2]

  if s < i:
    hq.heappush(Q, (T1[s>>1:i>>1], s,i))
  if i+1 < j:
    hq.heappush(Q, (T2[(i+1)>>1:j>>1], i+1,j))
  if j+1 < t:
    hq.heappush(Q, (T1[(j+1)>>1:t>>1], j+1,t))


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

Submission status: Time Limit Exceeded

Solution code:

from itertools import count,chain
from collections import deque
import heapq as hq

class MinSegTree:

  def __init__(self, inf, data=None, size=None):
    if data is None and size is None:
      raise Exception('data and size both cannot be None simultaneously')
    self.size = len(data) if size is None else size
    self.depth = (self.size-1).bit_length()
    self.capacity = 1 << self.depth
    self.inf = inf
    if data is None:
      self.data = [self.inf]*(2*self.capacity)
    else:
      self.data = [self.inf]*self.capacity + data + [self.inf]*(self.capacity-len(data))
      for d in reversed(range(self.depth)):
        t = 1 << d
        for i in range(t, 2*t):
          self.data[i] = min(self.data[2*i],self.data[2*i+1])

  def _min_interval(self, a, b):
    result = self.inf
    a += self.capacity
    b += self.capacity
    while a < b:
      if a & 1:
        result = min(result,self.data[a])
        a += 1
      if b & 1:
        b -= 1
        result = min(result,self.data[b])
      a >>= 1
      b >>= 1
    return result

  def _set_val(self, a, val):
    a += self.capacity
    while self.data[a] != val and a > 0:
      self.data[a] = val
      val = min(val,self.data[a^1])
      a >>= 1

  def __getitem__(self, i):
    if isinstance(i, slice):
      return self._min_interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop)
    elif isinstance(i, int):
      return self.data[i+self.capacity]

  def __setitem__(self, i, x):
    self._set_val(i,x)

  def __iter__(self):
    return iter(self.data[self.capacity:])



# from random import shuffle
# N = 2*10**5
# P = list(range(N))
# #shuffle(P)
N = int(input())
P = list(map(int,input().split()))

Te = MinSegTree((N+1,N), list(zip(P[::2], count(0,2))))
To = MinSegTree((N+2,N), list(zip(P[1::2], count(1,2))))


Q = [(0,0,N)]

ans = []

while Q:
  p,s,t = hq.heappop(Q)

  T1,T2 = (To,Te) if s&1 else (Te,To)

  a,b = s>>1,t>>1

  p1,i = T1[a:b]
  c = i >> 1
  p2,j = T2[c + (i&1):b + (t&1)]
  d = j >> 1

  ans += [p1,p2]

  if s < i:
    hq.heappush(Q, (T1[a:c][0], s,i))
  if i+1 < j:
    hq.heappush(Q, (T2[c + (i&1):d][0], i+1,j))
  if j+1 < t:
    hq.heappush(Q, (T1[d + (j&1):b][0], j+1,t))


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

Submission status: Time Limit Exceeded

Solution code:

from itertools import count,chain
from collections import deque
import heapq as hq

class MinSegTree:

  def __init__(self, inf, data=None, size=None):
    if data is None and size is None:
      raise Exception('data and size both cannot be None simultaneously')
    self.size = len(data) if size is None else size
    self.depth = (self.size-1).bit_length()
    self.capacity = 1 << self.depth
    self.inf = inf
    if data is None:
      self.data = [self.inf]*(2*self.capacity)
    else:
      self.data = [self.inf]*self.capacity + data + [self.inf]*(self.capacity-len(data))
      for d in reversed(range(self.depth)):
        t = 1 << d
        for i in range(t, 2*t):
          self.data[i] = min(self.data[2*i],self.data[2*i+1])

  def _min_interval(self, a, b):
    result = self.inf
    a += self.capacity
    b += self.capacity
    while a < b:
      if a & 1:
        result = min(result,self.data[a])
        a += 1
      if b & 1:
        b -= 1
        result = min(result,self.data[b])
      a >>= 1
      b >>= 1
    return result

  def _set_val(self, a, val):
    a += self.capacity
    while self.data[a] != val and a > 0:
      self.data[a] = val
      val = min(val,self.data[a^1])
      a >>= 1

  def __getitem__(self, i):
    if isinstance(i, slice):
      return self._min_interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop)
    elif isinstance(i, int):
      return self.data[i+self.capacity]

  def __setitem__(self, i, x):
    self._set_val(i,x)

  def __iter__(self):
    return iter(self.data[self.capacity:])


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

Te = MinSegTree((N+1,N), list(zip(P[::2], count(0,2))))
To = MinSegTree((N+2,N), list(zip(P[1::2], count(1,2))))


Q = [(0,0,N)]

ans = []

while Q:
  p,s,t = hq.heappop(Q)

  T1,T2 = (To,Te) if s%2 else (Te,To)

  p1,i = T1[s//2:t//2]
  p2,j = T2[(i+1)//2:(t+1)//2]

  ans += [p1,p2]

  if s < i:
    hq.heappush(Q, (T1[s//2:i//2][0], s,i))
  if i+1 < j:
    hq.heappush(Q, (T2[(i+1)//2:j//2][0], i+1,j))
  if j+1 < t:
    hq.heappush(Q, (T1[(j+1)//2:t//2][0], j+1,t))

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

Submission status: Time Limit Exceeded

Solution code:

from itertools import count,chain
from collections import deque
import sys

sys.setrecursionlimit(10**6)

class MinSegTree:

  def __init__(self, inf, data=None, size=None):
    if data is None and size is None:
      raise Exception('data and size both cannot be None simultaneously')
    self.size = len(data) if size is None else size
    self.depth = (self.size-1).bit_length()
    self.capacity = 1 << self.depth
    self.inf = inf
    if data is None:
      self.data = [self.inf]*(2*self.capacity)
    else:
      self.data = [self.inf]*self.capacity + data + [self.inf]*(self.capacity-len(data))
      for d in reversed(range(self.depth)):
        t = 1 << d
        for i in range(t, 2*t):
          self.data[i] = min(self.data[2*i],self.data[2*i+1])

  def _min_interval(self, a, b):
    result = self.inf
    a += self.capacity
    b += self.capacity
    while a < b:
      if a & 1:
        result = min(result,self.data[a])
        a += 1
      if b & 1:
        b -= 1
        result = min(result,self.data[b])
      a >>= 1
      b >>= 1
    return result

  def _set_val(self, a, val):
    a += self.capacity
    while self.data[a] != val and a > 0:
      self.data[a] = val
      val = min(val,self.data[a^1])
      a >>= 1

  def __getitem__(self, i):
    if isinstance(i, slice):
      return self._min_interval(
                  0 if i.start is None else i.start,
                  self.size if i.stop is None else i.stop)
    elif isinstance(i, int):
      return self.data[i+self.capacity]

  def __setitem__(self, i, x):
    self._set_val(i,x)

  def __iter__(self):
    return iter(self.data[self.capacity:])



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

Te = MinSegTree((N+1,N), list(zip(P[::2], count(0,2))))
To = MinSegTree((N+2,N), list(zip(P[1::2], count(1,2))))


def rec(s,t):
  # smallest x = A[i] where i is even
  # then smallest y = A[j] where j is odd
  if s >= t:
    return []

  #print(s,t)
  if s%2 == 0:
    p1,i = Te[s//2:t//2]
    p2,j = To[i//2:t//2]
  else:
    p1,i = To[s//2:t//2]
    p2,j = Te[i//2+1:t//2+1]

  # merge
  M = deque()
  M.append((p1,p2))

  X = [x for x in [rec(s,i), rec(i+1,j), rec(j+1,t)] if x]

  while X:
    x, k = min((x[0],k) for k,x in enumerate(X))
    M.append(x)
    X[k].popleft()
    if not X[k]:
      del X[k]
  
  # if X:
  #   M.extend(X[0])

  return M

ans = rec(0,N)

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

Submission status: Time Limit Exceeded

Solution code:
# E
import heapq

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

INT_MAX = N + 1

K2 = 0
N2 = 1

while N2 < N:
    N2 *= 2
    K2 += 1

# segtree
SGT_0 = []
SGT_1 = []
for k in range(K2+1):
    SGT_0.append([INT_MAX] * (N2 // (2**k)))
    SGT_1.append([INT_MAX] * (N2 // (2**k)))

# update
def update(i, a):
    global SGT_0
    global SGT_1
    if i % 2 == 0:
        j = i
        SGT_0[0][j] = a
        for k in range(1, K2+1):
            j = j // 2
            SGT_0[k][j] = min(SGT_0[k-1][2*j], SGT_0[k-1][2*j+1])
    else:
        j = i
        SGT_1[0][j] = a
        for k in range(1, K2+1):
            j = j // 2
            SGT_1[k][j] = min(SGT_1[k-1][2*j], SGT_1[k-1][2*j+1])
            
# query [a, b)
def query_min_0(a, b, k=K2, l=0, r=N2):
    # min in even numbers in [a, b)
    if r <= a or b <= l:
        return INT_MAX
    elif a <= l and r <= b:
        return SGT_0[k][l // (2**k)]
    else:
        vl = query_min_0(a, b, k-1, l, (l+r)//2)
        vr = query_min_0(a, b, k-1, (l+r)//2, r)
        return min(vl, vr)
    
def query_min_1(a, b, k=K2, l=0, r=N2):
    if r <= a or b <= l:
        return INT_MAX
    elif a <= l and r <= b:
        return SGT_1[k][l // (2**k)]
    else:
        vl = query_min_1(a, b, k-1, l, (l+r)//2)
        vr = query_min_1(a, b, k-1, (l+r)//2, r)
        return min(vl, vr)
    
def query_min_even(a, b, k=K2, l=0, r=N2):
    if a % 2 == 0:
        return query_min_0(a, b, k, l, r)
    else:
        return query_min_1(a, b, k, l, r)
    
def query_min_odd(a, b, k=K2, l=0, r=N2):
    if a % 2 == 1:
        return query_min_0(a, b, k, l, r)
    else:
        return query_min_1(a, b, k, l, r)
    
# initial value
# index_list
ind_list = [0]*(N+1)
for i in range(N):
    update(i, p_list[i])
    ind_list[p_list[i]] = i
    
# heapq
h0 = []
heapq.heapify(h0)
heapq.heappush(h0, (query_min_even(0, N), (0, N)))

q_list = []

for _ in range(N // 2):
    q0, (a, b) = heapq.heappop(h0)
    q_list.append(str(q0))
    c = ind_list[q0]
    q1 = query_min_odd(c, b)
    q_list.append(str(q1))
    d = ind_list[q1]
    if a < c:
        heapq.heappush(h0, (query_min_even(a, c), (a, c)))
    if c + 1 < d:
        heapq.heappush(h0, (query_min_even(c + 1, d), (c + 1, d)))
    if d < b:
        heapq.heappush(h0, (query_min_even(d + 1, b), (d + 1, b)))

print(" ".join(q_list))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
Pr = [int(n) for n in input().split()]

def extract(P):
    P_od = P[::2]
    P_st = P[1::2]
    odmin = min(P_od)
    odmin_idx = max([i if p == odmin else 0 for i , p in enumerate(P_od)])
    stmin = min(P_st[odmin_idx:])
    stmin_idx = max([i if p == stmin else 0 for i , p in enumerate(P_st)])
    
    P_left = []
    if odmin_idx != 0:
        for od, st in zip(P_od[:odmin_idx], P_st[:odmin_idx]):
            P_left.extend([od, st])
    P_right = []
    if stmin_idx != len(P_st): 
        for od, st in zip(P_od[stmin_idx+1:], P_st[stmin_idx+1:]):
            P_right.extend([od, st])
            
    ext_od = P_od[odmin_idx:stmin_idx+1]
    ext_st = P_st[odmin_idx:stmin_idx+1]
    ext = []
    for od, st in zip(ext_od, ext_st):
        ext.extend([od, st])
    extract = []
    for i in range(len(ext)//2):
        extract.append([ext[i], ext[::-1][i]])
    return extract, P_right, P_left

que = [Pr]
result = []

while len(que) > 0:
    ext, P_right, P_left = extract(que[0])
    ext_len = len(ext)
    j = 0
    new_result = []
    for res in result:
        if j < len(ext):
            while res[0] > ext[j][0]:
                new_result.append(ext[j])
                j += 1
                if j == len(ext):
                    break
        new_result.append(res)
    new_result.extend(ext[j:])
    result = new_result
    if len(P_right)!=0:
        que.append(P_right)
    if len(P_left)!=0:
        que.append(P_left)
    que = que[1:]

output = ""
for re in result:
    output += " {} {}".format(re[0], re[1])
print(output[1:])

Submission status: Time Limit Exceeded

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

q = []
summation = [p[i] + p[i + 1] for i in range(N - 1)]
for i in range(int(N / 2)):
    if len(p) == 2:
        q = p + q
    else:
        index = summation.index(max(summation))
        q = p[index:index + 2] + q
        p = p[:index] + p[index + 2:]
        if index == 0:
            summation = summation[2:]
        elif index == len(summation) - 1:
            summation = summation[:index - 1]
        else:
            summation = summation[:index - 1] + [p[index - 1] + p[index]] + summation[index + 2:]

[print(i, end=' ') for i in q]

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arrays = [[[], []]]
for i, p in enumerate(map(int, input().split())):
    arrays[0][i & 1].append((p, i))

ans = []
for _ in range(n // 2):
    (x, xi), ai = min((min(a[0]), ai) for ai, a in enumerate(arrays))
    xa, ya = arrays[ai]
    ans.append(x)
    if len(xa) == 1:
        ans.append(ya[0][0])
        arrays.pop(ai)
        continue
    xa0, ya0 = xa[0][1], ya[0][1]
    y, yi = min(ya[(xi - ya0 + 1) // 2:])
    ans.append(y)

    i1 = (xi - xa0) // 2
    i2 = (yi - ya0) // 2
    f1, f2, f3 = i1 > 0, i1 != i2, i2 + 1 < len(xa)
    if f1:
        arrays[ai] = [xa[:i1], ya[:i1]]
        if f2:
            arrays.append([ya[i1:i2], xa[i1 + 1:i2 + 1]])
        if f3:
            arrays.append([xa[i2 + 1:], ya[i2 + 1:]])
    else:
        if f2:
            arrays[ai] = [ya[i1:i2], xa[i1 + 1:i2 + 1]]
            if f3:
                arrays.append([xa[i2 + 1:], ya[i2 + 1:]])
        else:
            arrays[ai] = [xa[i2 + 1:], ya[i2 + 1:]]

print(*ans)

Submission status: Time Limit Exceeded

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

q = []
for i in range(int(N / 2)):
    summation = [p[j] + p[j + 1] for j in range(N - i * 2 - 1)]
    index = summation.index(max(summation))
    q = p[index:index + 2] + q
    p = p[:index] + p[index + 2:]

[print(i, end=' ') for i in q]

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int,input().split()))

from itertools import count,chain
from collections import deque

def rec(A):
  # smallest x = A[i] where i is even
  # then smallest y = A[j] where j is odd
  if not A:
    return A
  
  p1,i = min(zip(A[:-1:2], count(0,2)))
  p2,j = min(zip(A[i+1::2], count(i+1,2)))
  # merge

  X = [x for x in [rec(A[:i]), rec(A[i+1:j]), rec(A[j+1:])] if x]

  M = deque()
  M.append((p1,p2))

  while X:
    x, k = min((x[0],k) for k,x in enumerate(X))
    M.append(x)
    X[k].popleft()
    if not X[k]:
      del X[k]

  return M

ans = rec(P)

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

Submission status: Accepted

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

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

    return res


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

        self.n = len(x)

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

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

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

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

        return res

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

        self.n = len(x)

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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)

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)
    
    #print(v,p[l])
        
    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)



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

Submission status: Accepted

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

Submission status: Accepted

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

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


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

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

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

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            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)

Submission status: Accepted

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


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

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

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

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            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)