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:
# 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):
    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: 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)
    for i in range(n):
        data[n0-1+i] = P[i]
    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):
    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+1)//2, (r+1)//2)
    else:
        y = get(d0, (l+1)//2, (r+1)//2)
    return y

from heapq import heappush, heappop
que = [(min(P[0::2]), 0, N)]
ans = []
while que:
    x, l, r = heappop(que)
    y = query_y(l, r)

    xi = M[x]; 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))

    ans.append("%d %d" % (x, y))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
raw_input()
l = map(int, raw_input().split())
memo = {}
c = 0

def get_min(l):
    if len(l) == 2:
        return l[0], 0, l[1], 1
    if (l[0], l[-1]) in memo:
        return memo[(l[0], l[-1])]

    e_l = []
    o_l = []
    for i, val in enumerate(l):
        if i % 2 == 0:
            e_l.append((val, i))
        else:
            o_l.append((val, i))

    first_val, first_idx = min(e_l)
    o_l = [(val, i) for val, i in o_l if i > first_idx]
    second_val, second_idx = min(o_l)

    ret = (first_val, first_idx, second_val, second_idx)
    memo[(l[0], l[-1])] = ret
    return ret

ls = [l]
while (len(ls) > 0):
    first_val = -1
    for lidx, l in enumerate(ls):
        _first_val, _first_idx, _second_val, _second_idx = get_min(l)
        if _first_val < first_val or first_val < 0:
            first_val = _first_val
            first_idx = _first_idx
            second_val = _second_val
            second_idx = _second_idx
            _lidx = lidx
    print first_val, second_val,
    _l = ls.pop(_lidx)
    if first_idx > 0:
        ls.append(_l[:first_idx])
    if first_idx + 2 < second_idx:
        ls.append(_l[first_idx + 1:second_idx])
    if second_idx + 1< len(_l):
        ls.append(_l[second_idx + 1:])

print

Submission status: Time Limit Exceeded

Solution code:
raw_input()
l = map(int, raw_input().split())
memo = {}
 
def get_min(l):
    if (l[0], l[-1]) in memo:
        return memo[(l[0], l[-1])]
    r = [(_, idx) for idx, _ in enumerate(l) if idx % 2 == 0]
    first_val, first_idx = min(r)
    r = [(_, idx) for idx, _ in enumerate(l) if idx % 2 != 0 and idx > first_idx]
    second_val, second_idx = min(r)
    ret = (first_val, first_idx, second_val, second_idx)
    memo[(l[0], l[-1])] = ret
    return ret
 
ls = [l]
while (len(ls) > 0):
    first_val = -1
    for lidx, l in enumerate(ls):
        _first_val, _first_idx, _second_val, _second_idx = get_min(l)
        if _first_val < first_val or first_val < 0:
            first_val, first_idx, second_val, second_idx = get_min(l)
            _lidx = lidx
    print first_val, second_val,
    _l = ls.pop(_lidx)
    if first_idx > 0:
        ls.append(_l[:first_idx])
    if first_idx + 2 < second_idx:
        ls.append(_l[first_idx + 1:second_idx])
    if second_idx + 1< len(_l):
        ls.append(_l[second_idx + 1:])
 
print

Submission status: Time Limit Exceeded

Solution code:
raw_input()
l = map(int, raw_input().split())
memo = {}

def get_min(l):
    if (l[0], l[-1]) in memo:
        return memo[(l[0], l[-1])]
    r = [(_, idx) for idx, _ in enumerate(l) if idx % 2 == 0]
    first_val, first_idx = min(r)
    r = [(_, idx) for idx, _ in enumerate(l) if idx % 2 != 0 and idx > first_idx]
    second_val, second_idx = min(r)
    ret = (first_val, first_idx, second_val, second_idx)
    memo[(l[0], l[-1])] = ret
    return ret

ls = [l]
while (len(ls) > 0):
    vals = []
    for lidx, l in enumerate(ls):
        first_val, first_idx, second_val, second_idx = get_min(l)
        vals.append((first_val, first_idx, second_val, second_idx, lidx))
    first_val, first_idx, second_val, second_idx, lidx = min(vals)
    print first_val, second_val,
    _l = ls.pop(lidx)
    if first_idx > 0:
        ls.append(_l[:first_idx])
    if first_idx + 2 < second_idx:
        ls.append(_l[first_idx + 1:second_idx])
    if second_idx + 1< len(_l):
        ls.append(_l[second_idx + 1:])

print

Submission status: Time Limit Exceeded

Solution code:
raw_input()
l = map(int, raw_input().split())

def get_min(l):
    r = [(_, idx) for idx, _ in enumerate(l) if idx % 2 == 0]
    first_val, first_idx = min(r)
    r = [(_, idx) for idx, _ in enumerate(l) if idx % 2 != 0 and idx > first_idx]
    second_val, second_idx = min(r)
    return first_val, first_idx, second_val, second_idx

ls = [l]
while (len(ls) > 0):
    vals = []
    for lidx, l in enumerate(ls):
        first_val, first_idx, second_val, second_idx = get_min(l)
        vals.append((first_val, first_idx, second_val, second_idx, lidx))
    first_val, first_idx, second_val, second_idx, lidx = min(vals)
    print first_val, second_val,
    _l = ls.pop(lidx)
    if first_idx > 0:
        ls.append(_l[:first_idx])
    if first_idx + 2 < second_idx:
        ls.append(_l[first_idx + 1:second_idx])
    if second_idx + 1< len(_l):
        ls.append(_l[second_idx + 1:])

print

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n = I()
    a = LI()

    def sf(a,b):
        if a < b:
            return a
        return b

    s1 = Seg([c if i%2==0 else inf for c,i in zip(a,range(n))],inf,sf)
    s2 = Seg([c if i%2==1 else inf for c,i in zip(a,range(n))],inf,sf)
    d = {}

    for i in range(n):
        d[a[i]] = i

    def f(l,r):
        if l % 2 == 0:
            t = s1.query(l,r)
            ti = d[t]
            u = s2.query(ti+1,r)
        else:
            t = s2.query(l,r)
            ti = d[t]
            u = s1.query(ti+1,r)
        ui = d[u]
        nl = []
        if l < ti:
            nl.append((l, ti))
        if ui - ti > 1:
            nl.append((ti+1, ui))
        if ui < r-1:
            nl.append((ui+1, r))
        return ((t,u), nl)

    q = []
    heapq.heappush(q, f(0,n))
    r = []
    while q:
        t,nl = heapq.heappop(q)
        r.append(t[0])
        r.append(t[1])
        for t,u in nl:
            heapq.heappush(q, f(t,u))

    return ' '.join(map(str,r))

print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N-1) + na + [default] * (self.N-n)
            for i in range(self.N-2,-1,-1):
                self.A[i] = func(self.A[i*2+1], self.A[i*2+2])
        else:
            self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        b += 1
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)

def main():
    n = I()
    a = LI()

    def sf(a,b):
        if a < b:
            return a
        return b

    s1 = Seg([c if i%2==0 else inf for c,i in zip(a,range(n))],inf,sf)
    s2 = Seg([c if i%2==1 else inf for c,i in zip(a,range(n))],inf,sf)
    d = {}

    for i in range(n):
        d[a[i]] = i

    def f(l,r):
        if l % 2 == 0:
            t = s1.query(l,r)
            ti = d[t]
            u = s2.query(ti+1,r)
        else:
            t = s2.query(l,r)
            ti = d[t]
            u = s1.query(ti+1,r)
        ui = d[u]
        nl = []
        if l < ti:
            nl.append((l, ti-1))
        if ui - ti > 1:
            nl.append((ti+1, ui-1))
        if ui < r:
            nl.append((ui+1, r))
        return ((t,u), nl)

    q = []
    heapq.heappush(q, f(0,n-1))
    r = []
    while q:
        t,nl = heapq.heappop(q)
        r.append(t[0])
        r.append(t[1])
        for t,u in nl:
            heapq.heappush(q, f(t,u))

    return ' '.join(map(str,r))

print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = math.ceil(math.log2(n))
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N-1) + na + [default] * (self.N-n)
            for i in range(self.N-2,-1,-1):
                self.A[i] = func(self.A[i*2+1], self.A[i*2+2])
        else:
            self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        b += 1
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)

def main():
    n = I()
    a = LI()

    def sf(a,b):
        if a < b:
            return a
        return b

    s1 = Seg([c if i%2==0 else inf for c,i in zip(a,range(n))],inf,sf)
    s2 = Seg([c if i%2==1 else inf for c,i in zip(a,range(n))],inf,sf)
    d = {}

    for i in range(n):
        d[a[i]] = i

    def f(l,r):
        if l % 2 == 0:
            t = s1.query(l,r)
            ti = d[t]
            u = s2.query(ti+1,r)
        else:
            t = s2.query(l,r)
            ti = d[t]
            u = s1.query(ti+1,r)
        ui = d[u]
        nl = []
        if l < ti:
            nl.append((l, ti-1))
        if ui - ti > 1:
            nl.append((ti+1, ui-1))
        if ui < r:
            nl.append((ui+1, r))
        return ((t,u), nl)

    q = []
    heapq.heappush(q, f(0,n-1))
    r = []
    while q:
        t,nl = heapq.heappop(q)
        r.append(t[0])
        r.append(t[1])
        for t,u in nl:
            heapq.heappush(q, f(t,u))

    return ' '.join(map(str,r))

print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, n, default, func):
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        b += 1
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)

def main():
    n = I()
    a = LI()

    def sf(a,b):
        if a < b:
            return a
        return b

    s1 = Seg(n,inf,sf)
    s2 = Seg(n,inf,sf)
    d = {}

    for i in range(n):
        if i % 2 == 0:
            s1.update(i, a[i])
        else:
            s2.update(i, a[i])
        d[a[i]] = i

    def f(l,r):
        if l % 2 == 0:
            t = s1.query(l,r)
            ti = d[t]
            u = s2.query(ti+1,r)
        else:
            t = s2.query(l,r)
            ti = d[t]
            u = s1.query(ti+1,r)
        ui = d[u]
        nl = []
        if l < ti:
            nl.append((l, ti-1))
        if ui - ti > 1:
            nl.append((ti+1, ui-1))
        if ui < r:
            nl.append((ui+1, r))
        return ((t,u), nl)

    q = []
    heapq.heappush(q, f(0,n-1))
    r = []
    while q:
        t,nl = heapq.heappop(q)
        r.append(t[0])
        r.append(t[1])
        for t,u in nl:
            heapq.heappush(q, f(t,u))

    return ' '.join(map(str,r))

print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, n, default, func):
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        b += 1
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)

def main():
    n = I()
    a = LI()

    def sf(a,b):
        if a < b:
            return a
        return b

    s1 = Seg(n,(inf,-1),sf)
    s2 = Seg(n,(inf,-1),sf)

    for i in range(n):
        if i % 2 == 0:
            s1.update(i, (a[i], i))
        else:
            s2.update(i, (a[i], i))

    def f(l,r):
        if l % 2 == 0:
            t = s1.query(l,r)
            u = s2.query(t[1]+1,r)
        else:
            t = s2.query(l,r)
            u = s1.query(t[1]+1,r)
        nl = []
        if l < t[1]:
            nl.append((l, t[1]-1))
        if u[1] - t[1] > 1:
            nl.append((t[1]+1, u[1]-1))
        if u[1] < r:
            nl.append((u[1]+1, r))
        return ((t[0],u[0]), nl)

    q = []
    heapq.heappush(q, f(0,n-1))
    r = []
    while q:
        t,nl = heapq.heappop(q)
        r.append(t[0])
        r.append(t[1])
        for t,u in nl:
            heapq.heappush(q, f(t,u))

    return ' '.join(map(str,r))

print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class Seg():
    def __init__(self, n, default, func):
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        self.A = [default] * (self.N*2-1)
        self.F = func

    def find(self, i):
        return self.A[i + self.N - 1]

    def update(self, i, x):
        i += self.N - 1
        self.A[i] = x
        while i > 0:
            i = (i-1) // 2
            self.A[i] = self.merge(self.A[i*2+1], self.A[i*2+2])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[0]

    def query(self, a, b):
        b += 1
        def _query(k,l,r):
            if r <= a or b <= l:
                return self.D
            if a <= l and r <= b:
                return self.A[k]
            m = (l+r)//2
            vl = _query(k*2+1,l,m)
            vr = _query(k*2+2,m,r)
            return self.merge(vl,vr)
        return _query(0,0,self.N)

def main():
    n = I()
    a = LI()

    def sf(a,b):
        if a < b:
            return a
        return b

    s1 = Seg(n,(inf,-1),sf)
    s2 = Seg(n,(inf,-1),sf)

    for i in range(n):
        if i % 2 == 0:
            s1.update(i, (a[i], i))
        else:
            s2.update(i, (a[i], i))

    def f(l,r):
        if l % 2 == 0:
            t = s1.query(l,r)
            u = s2.query(t[1]+1,r)
        else:
            t = s2.query(l,r)
            u = s1.query(t[1]+1,r)
        nl = []
        if l < t[1]:
            nl.append((l, t[1]-1))
        if u[1] - t[1] > 1:
            nl.append((t[1]+1, u[1]-1))
        if u[1] < r:
            nl.append((u[1]+1, l))
        return ((t[0],u[0]), nl)

    q = []
    heapq.heappush(q, f(0,n-1))
    r = []
    while q:
        t,nl = heapq.heappop(q)
        r.append(t[0])
        r.append(t[1])
        for t,u in nl:
            heapq.heappush(q, f(t,u))

    return ' '.join(map(str,r))

print(main())

Submission status: Time Limit Exceeded

Solution code:
import heapq
 
class SegTree:
    
    def __init__(self):
        self.n=2**18
        self.inf=(9999999,-1)
        self.tree=[self.inf for i in range(self.n*2)]
        
    def update(self,index,x):
        index+=self.n
        self.tree[index]=x
        while index>1:
            index//=2
            self.tree[index]=min(self.tree[index*2],self.tree[index*2+1])
            
    def query(self,a,b,k,l,r):
        if a<=l and r<=b:
            return self.tree[k]
        if r<=a or b<=l:
            return self.inf 
        return min(self.query(a,b,k*2,l,(l+r)//2),self.query(a,b,k*2+1,(l+r)//2,r))
    
    def q(self,a,b):
        return self.query(a,b,1,0,self.n)
 
n=int(input()) 
p=list(map(int,input().split()))
 
k=SegTree()     
g=SegTree()
 
for index,i in enumerate(p):
    if index%2==0:
        g.update(index,(i,index))
    else:
        k.update(index,(i,index))
 
q=[]
heap=[]
heapq.heappush(heap,(g.q(0,n),0,n))
while len(heap)>0:
    t=heapq.heappop(heap)
    a=t[0]
    l=t[1]
    r=t[2]
    if l%2==0:  
        kk=k.q(a[1],r)
        if a[1]-l>=2:
            heapq.heappush(heap,(g.q(l,a[1]),l,a[1]))
        if kk[1]-(a[1]+1)>=2:
            heapq.heappush(heap,(k.q(a[1]+1,kk[1]),a[1]+1,kk[1]))
        if r-(kk[1]+1)>=2:
            heapq.heappush(heap,(g.q(kk[1]+1,r),kk[1]+1,r))
    else:
        kk=g.q(a[1],r)
        if a[1]-l>=2:
            heapq.heappush(heap,(k.q(l,a[1]),l,a[1]))
        if kk[1]-(a[1]+1)>=2:
            heapq.heappush(heap,(g.q(a[1]+1,kk[1]),a[1]+1,kk[1]))
        if r-(kk[1]+1)>=2:
            heapq.heappush(heap,(k.q(kk[1]+1,r),kk[1]+1,r))
    q.append(a[0])
    q.append(kk[0])
        
        
    
print(" ".join(list(map(str,q))))

Submission status: Time Limit Exceeded

Solution code:
import heapq
 
class SegTree:
    
    def __init__(self):
        self.n=2**18
        self.inf=(9999999,-1)
        self.tree=[self.inf for i in range(self.n*2)]
        
    def update(self,index,x):
        index+=self.n
        self.tree[index]=x
        while index>1:
            index//=2
            self.tree[index]=min(self.tree[index*2],self.tree[index*2+1])
            
    def query(self,a,b,k,l,r):
        if a<=l and r<=b:
            return self.tree[k]
        if r<=a or b<=l:
            return self.inf 
        return min(self.query(a,b,k*2,l,(l+r)//2),self.query(a,b,k*2+1,(l+r)//2,r))
    def q(self,a,b):
        return self.query(a,b,1,0,self.n)
 
n=int(input()) 
p=list(map(int,input().split()))
 
k=SegTree()     
g=SegTree()
 
for index,i in enumerate(p):
    if index%2==0:
        g.update(index,(i,index))
    else:
        k.update(index,(i,index))
 
q=[]
heap=[]
heapq.heappush(heap,(g.q(0,n),0,n))
while len(heap)>0:
    t=heapq.heappop(heap)
    a=t[0]
    l=t[1]
    r=t[2]
    if r-l<2:
        continue
    if l%2==0:  
        kk=k.q(a[1],r)
        heapq.heappush(heap,(g.q(l,a[1]),l,a[1]))
        heapq.heappush(heap,(k.q(a[1]+1,kk[1]),a[1]+1,kk[1]))
        heapq.heappush(heap,(g.q(kk[1]+1,r),kk[1]+1,r))
    else:
        kk=g.q(a[1],r)
        heapq.heappush(heap,(k.q(l,a[1]),l,a[1]))
        heapq.heappush(heap,(g.q(a[1]+1,kk[1]),a[1]+1,kk[1]))
        heapq.heappush(heap,(k.q(kk[1]+1,r),kk[1]+1,r))
    q.append(a[0])
    q.append(kk[0])
        
        
    
print(" ".join(list(map(str,q))))

Submission status: Time Limit Exceeded

Solution code:
import heapq

class SegTree:
    
    def __init__(self):
        self.n=2**18
        self.inf=(9999999,-1)
        self.tree=[self.inf for i in range(self.n*2)]
        
    def update(self,index,x):
        index+=self.n
        self.tree[index]=x
        while index>1:
            index//=2
            self.tree[index]=min(self.tree[index*2],self.tree[index*2+1])
            
    def query(self,a,b,k,l,r):
        if a<=l and r<=b:
            return self.tree[k]
        if r<=a or b<=l:
            return self.inf 
        return min(self.query(a,b,k*2,l,(l+r)//2),self.query(a,b,k*2+1,(l+r)//2,r))
    def q(self,a,b):
        return self.query(a,b,1,0,self.n)

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

k=SegTree()     
g=SegTree()

for index,i in enumerate(p):
    if index%2==0:
        g.update(index,(i,index))
    else:
        k.update(index,(i,index))

q=[]
heap=[]
heapq.heappush(heap,(g.q(0,n),0,n))
while len(heap)>0:
    t=heapq.heappop(heap)
    a=t[0]
    l=t[1]
    r=t[2]
    if r-l<2:
        continue
    if l%2==0:  
        kk=k.q(a[1],r)
        heapq.heappush(heap,(g.q(l,a[1]),l,a[1]))
        heapq.heappush(heap,(k.q(a[1]+1,kk[1]),a[1]+1,kk[1]))
        heapq.heappush(heap,(g.q(kk[1]+1,r),kk[1]+1,r))
    else:
        kk=g.q(a[1],r)
        heapq.heappush(heap,(k.q(l,a[1]),l,a[1]))
        heapq.heappush(heap,(g.q(a[1]+1,kk[1]),a[1]+1,kk[1]))
        heapq.heappush(heap,(k.q(kk[1]+1,r),kk[1]+1,r))
    q.append(a[0])
    q.append(kk[0])
        
        
    
print(" ".join(list(map(str,q))))