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 collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class Segtree:
    def __init__(self, A, ide_ele, segf, initialize=True):
        self.N = len(A)
        self.N0 = 2 ** (self.N - 1).bit_length()
        self.ide_ele = ide_ele
        self.segf = segf
        if initialize:
            self.data = [ide_ele] * self.N0 + A + [ide_ele] * (self.N0 - self.N)
            for i in range(self.N0 - 1, 0, -1):
                self.data[i] = self.segf(self.data[2 * i], self.data[2 * i + 1])
        else:
            self.data = [ide_ele] * (2 * self.N0)

    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0:
            k = k >> 1
            self.data[k] = self.segf(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.N0, r + self.N0
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

n = I()
P = LI()
D = {P[i]:i for i in range(n)}
p_even = [P[i] if not i % 2 else INF for i in range(n)]
p_odd = [P[i] if i % 2 else INF for i in range(n)]
st_even = Segtree(p_even, INF, min)
st_odd = Segtree(p_odd, INF, min)
hq = [(st_even.query(0, n), 0, n)]
ans = []
for i in range(n // 2):
    v1, l, r = heappop(hq)
    p1 = D[v1]
    if not l & 1:
        st1, st2 = st_odd, st_even
    else:
        st1, st2 = st_even, st_odd
    v2 = st1.query(p1, r)
    p2 = D[v2]
    st2.update(p1, INF)
    st1.update(p2, INF)
    if l != p1:
        heappush(hq, (st2.query(l, p1), l, p1))
    if p1 + 1 != p2:
        heappush(hq, (st1.query(p1 + 1, p2), p1 + 1, p2))
    if p2 + 1 != r:
        heappush(hq, (st2.query(p2 + 1, r), p2 + 1, r))
    ans += [v1,  v2]


print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class SegmentTree:
    def __init__(self, n, ide_ele, op, init_val=[]):
        self.n = 2 ** (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.op = op
        self.seg = [ide_ele] * 2 * self.n
        if init_val:
            for i in range(n):
                self.seg[i + self.n - 1] = init_val[i]
            for i in range(self.n - 2, -1, -1):
                self.seg[i] = self.op(self.seg[2 * i + 1], self.seg[2 * i + 2])

    def update(self, k, x):
        k += self.n - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.op(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, p, q):
        # qは含まない
        if q <= p:
            return self.ide_ele
        p += self.n - 1
        q += self.n - 2
        res = self.ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res


n = I()
P = LI()
D = {P[i]:i for i in range(n)}
p_even = [P[i] if not i % 2 else INF for i in range(n)]
p_odd = [P[i] if i % 2 else INF for i in range(n)]
st_even = SegmentTree(n, INF, min, init_val=p_even)
st_odd = SegmentTree(n, INF, min, init_val=p_odd)
st_list = [st_even, st_odd]
hq = [(st_even.query(0, n), 0, n)]
ans = []
for i in range(n // 2):
    v1, l, r = heappop(hq)
    p1 = D[v1]
    if not l & 1:
        st1, st2 = st_odd, st_even
    else:
        st1, st2 = st_even, st_odd
    v2 = st1.query(p1, r)
    p2 = D[v2]
    st2.update(p1, INF)
    st1.update(p2, INF)
    if l != p1:
        heappush(hq, (st2.query(l, p1), l, p1))
    if p1 + 1 != p2:
        heappush(hq, (st1.query(p1 + 1, p2), p1 + 1, p2))
    if p2 + 1 != r:
        heappush(hq, (st2.query(p2 + 1, r), p2 + 1, r))
    ans += [v1,  v2]


print(*ans)

Submission status: Time Limit Exceeded

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]*(2*self.N0)
        self.fun = fun
    def update(self, k, x, update_fun):
        k+=self.N0-1
        self.data[k] = update_fun(self.data[k], x)
        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
        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
def main():
    import sys
    input = sys.stdin.readline
    inf = 10**18
    N = int(input())
    p = list(map(int, input().split()))
    d = [0]*(N+1)
    for i in range(N):
        d[p[i]] = i
    S1 = SegmentTree(N//2, inf, min)
    S2 = SegmentTree(N//2, inf, min)
    res = []
    def add(l, r):
        if r-l<2:
            return
        if l%2 == 0:
            x = S1.query(l//2, r//2)
            i = d[x]
        else:
            x = S2.query(l//2, r//2)
            i = d[x]
        heappush(que, (x, i, l, r))

    from heapq import heappop, heappush
    f = lambda x, y:y
    for i, x in enumerate(p[::2]):
        S1.update(i, x, f)
    for i, x in enumerate(p[1::2]):
        S2.update(i, x, f)
    x = S1.query(0, N//2)
    i = d[x]
    que = [(x, i, 0, N)]
    while que:
        x, i, l, r = heappop(que)
        if r-l==2:
            res.append(p[l])
            res.append(p[l+1])
            continue
        if r-l<2:
            continue
        if l%2 == 0:
            y = S2.query(i//2, r//2)
            j = d[y]
        else:
            y = S1.query(i//2+1, r//2+1)
            j = d[y]
        res.append(x)
        res.append(y)
        add(l, i)
        add(i+1, j)
        add(j+1, r)
    print(*res)
main()

Submission status: Time Limit Exceeded

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, -1)]*(2*self.N0)
        self.fun = fun
    def update(self, i, x):
        k=i+self.N0-1
        self.data[k] = (x, i)
        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, -1)
        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
def main():
    import sys
    #input = sys.stdin.readline
    inf = 10**18
    N = int(input())
    p = list(map(int, input().split()))
    S1 = SegmentTree(N//2, inf, min)
    S2 = SegmentTree(N//2, inf, min)
    res = []
    def add(l, r):
        if l%2 == 0:
            x, i = S1.query(l//2, r//2)
            i = i*2
        else:
            x, i = S2.query(l//2, r//2)
            i = i*2+1
        heappush(que, (x, i, l, r))

    from heapq import heappop, heappush
    for i, x in enumerate(p[::2]):
        S1.update(i, x)
    for i, x in enumerate(p[1::2]):
        S2.update(i, x)
    x, i = S1.query(0, N//2)
    que = [(x, i*2, 0, N)]
    while que:
        x, i, l, r = heappop(que)
        if r-l==2:
            res.append(p[l])
            res.append(p[l+1])
            continue
        if r-l<2:
            continue
        if l%2 == 0:
            y, j = S2.query(i//2, r//2)
            j = j*2+1
        else:
            y, j = S1.query(i//2+1, r//2+1)
            j = j*2
        res.append(x)
        res.append(y)
        add(l, i)
        add(i+1, j)
        add(j+1, r)
    print(*res)
main()

Submission status: Time Limit Exceeded

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, -1)]*(2*self.N0)
        self.fun = fun
    def update(self, i, x):
        k=i+self.N0-1
        self.data[k] = (x, i)
        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, -1)
        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)
res = []
def add(l, r):
    if l%2 == 0:
        x, i = S1.query(l//2, r//2)
        i = i*2
    else:
        x, i = S2.query(l//2, r//2)
        i = i*2+1
    heappush(que, (x, i, l, r))

from heapq import heappop, heappush
for i, x in enumerate(p[::2]):
    S1.update(i, x)
for i, x in enumerate(p[1::2]):
    S2.update(i, x)
x, i = S1.query(0, N//2)
que = [(x, i*2, 0, N)]
while que:
    x, i, l, r = heappop(que)
    if r-l==2:
        res.append(p[l])
        res.append(p[l+1])
        continue
    if r-l<2:
        continue
    if l%2 == 0:
        y, j = S2.query(i//2, r//2)
        j = j*2+1
    else:
        y, j = S1.query(i//2+1, r//2+1)
        j = j*2
    res.append(x)
    res.append(y)
    add(l, i)
    add(i+1, j)
    add(j+1, r)
print(*res)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys

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

class SegtreeMin():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 1 << (n - 1).bit_length()
        self.tree_width = tree_width
        self.tree = [self.inf] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def refresh(self):
        for seg_i in range(self.tree_width - 2, -1, -1):
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    # [l,r)の最小値
    def min(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
        return min(ret0, ret1)

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

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys

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

class SegtreeMin():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 1 << (n - 1).bit_length()
        self.tree_width = tree_width
        self.tree = [self.inf] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def refresh(self):
        for seg_i in range(self.tree_width - 2, -1, -1):
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    # [l,r)の最小値
    def min(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
        return min(ret0, ret1)

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

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys

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

class SegtreeMin():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 1 << n.bit_length()
        self.tree_width = tree_width
        self.tree = [self.inf] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最小値
    def min(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
        return min(ret0, ret1)

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

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys

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

class SegtreeMin():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 2
        while tree_width < n:
            tree_width *= 2
        self.tree_width = tree_width
        self.tree = [self.inf] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最小値
    def min(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
        return min(ret0, ret1)

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

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
INF = 10**30

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

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

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

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

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

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

d = dict()

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

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

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

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

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

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

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
INF = 10**30

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

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

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

	#[a, b)
	def Get(self, a, b, k=0, l=0, r=-1):
		if r < 0:
			r = self.n

		if a >= r or b <= l:
			return INF
		elif a <= l and b >= r:
			return self.node[k]
		else:
			vl = self.Get(a, b, 2*k+1, l, (l+r)//2)
			vr = self.Get(a, b, 2*k+2, (l+r)//2, r)
			return min(vl, vr)

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

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

d = dict()

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

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

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

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

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

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

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import tee
import sys

sys.setrecursionlimit(10 ** 7)
inf = float('inf')


def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)  # Noneはイテレータが尽きた場合に返すdefault/指定しなければStopIteration
    return zip(a, b)


def rec(lst, lg):
    if lg == 2: return lst
    idx = -1
    t = None
    mp = -1
    Mp = -1
    for i, p in enumerate(pairwise(lst)):
        if min(p) > mp or (min(p) == mp and max(p) > Mp):
            t = p
            mp = min(p)
            Mp = max(p)
            idx = i
    # print(idx)
    return rec(lst[:idx] + lst[idx + 2:], lg - 2) + t


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

print(*rec(p, N))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import heapq

INT_MAX = 10 ** 9

class SegTreeX:

    def __init__(self, n):
        k = 1
        while k < n:
            k *= 2

        self.n = n = k
        self.dat = [INT_MAX] * (n * 2)
        self.pos = [i - n + 1 for i in range(n * 2)]


    def update(self, i, x):
        i += self.n - 1
        self.dat[i] = x
        while 0 < i:
            i = (i - 1) // 2
            d1 = self.dat[i * 2 + 1]
            d2 = self.dat[i * 2 + 2]
            if d1 < d2:
                self.dat[i] = d1
                self.pos[i] = self.pos[i * 2 + 1]
            else:
                self.dat[i] = d2
                self.pos[i] = self.pos[i * 2 + 2]


    def query(self, a, b, k = 0, l = 0, r = -1):
        if r < 0:
            r = self.n
        if r <= a or b <= l:
            return INT_MAX, -1
        if a <= l and r <= b:
            return self.dat[k], self.pos[k]
        else:
            vl, pl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr, pr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            if vl < vr:
                return vl, pl
            else:
                return vr, pr


def solve(n, p):

    seg = [SegTreeX(n) for _ in range(2)]
    for i in range(0, n, 2):
        seg[0].update(i, p[i])
    for i in range(1, n, 2):
        seg[1].update(i, p[i])

    ans = []
    q = []
    a, i = seg[0].query(0, n)
    b, j = seg[1].query(i, n)
    heapq.heappush(q, (a, b, 0, n, i, j, 0))
    while q:
        a, b, l, r, i, j, f = heapq.heappop(q)
        ans.append(a)
        ans.append(b)
        if l < i - 1:
            al, il = seg[f].query(l, i)
            bl, jl = seg[1 - f].query(il, i)
            heapq.heappush(q, (al, bl, l, i - 1, il, jl, f))
        if i + 1 < j - 1:
            am, im = seg[1 - f].query(i + 1, j)
            bm, jm = seg[f].query(im, j)
            heapq.heappush(q, (am, bm, i + 1, j - 1, im, jm, 1 - f))
        if j + 1 < r - 1:
            ar, ir = seg[f].query(j + 1, r)
            br, jr = seg[1 - f].query(ir, r)
            heapq.heappush(q, (ar, br, j + 1, r, ir, jr, f))

    return ans


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


    print(' '.join(list(map(str, solve(n, p)))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)

K = 4
def get(data, l, r):
    n0 = len(data)//2
    if r-l <= K:
        return min(data[n0-1+l:n0-1+r])
    return __get(data, l, r, 0, 0, n0)

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)