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: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp
class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(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 = [intv]*(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.intv
        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
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

N = int(readline())

inf = 1<<32
P = list(map(int, readline().split()))

Pi = [None]*(N+1)
for i in range(N):
    Pi[P[i]] = i

inf = 1<<32
Peven = [P[i] if not i&1 else inf for i in range(N)]
Podd = [P[i] if i&1 else inf for i in range(N)]

Teven = Segtree(Peven, inf, initialize = True, segf = min)
Todd = Segtree(Podd, inf, initialize = True, segf = min)
N0 = 2**(N-1).bit_length()

Q = [(Teven.query(0, N0), 0, N0)]
for i in range(N//2):
    t1, l, r = hpp(Q)
    K = []
    if not l&1:
        p1 = Pi[t1]
        t2 = Todd.query(l, r)
        p2 = Pi[t2]
        Teven.update(p1, inf)
        Todd.update(p2, inf)
    else:
        p1 = Pi[t1]
        t2 = Teven.query(l, r)
        p2 = Pi[t2]
        Todd.update(p1, inf)
        Teven.update(p2, inf)
    if l < p1:
        K.append((l, p1))
    if p2 < r:
        K.append((p2+1, r))
    if p1 + 1 < p2:
        K.append((p1+1, p2))
    for l, r in K:
        if not l&1:
            mq = Teven.query(l, r)
        else:
            mq = Todd.query(l, r)
        hp(Q, (mq, l, r))
    sys.stdout.write('{} {} '.format(t1, t2))
sys.stdout.write('\n')

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
class Dualsegtree:
    def __init__(self, A, intv, initialize = True):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = min
        if initialize:
            self.data = [intv]*(self.N0-1) + A + [intv]*(self.N0 - self.N + 1)
            for i in range(self.N0-2, -1, -1):
                self.data[i] = self.segf(self.data[2*i+1], self.data[2*i+2]) 
        else:
            self.data = [intv]*(2*self.N0)
                
    def query(self, k):
        k += self.N0-1
        s = self.data[k]
        while k >= 0 :
            k = (k-1) >> 1
            s = self.segf(s, self.data[k])
        return s
    
    def update(self, l, r, x):
        L, R = l+self.N0, r+self.N0
        while L < R:
            if R & 1:
                R -= 1
                self.data[R-1] = self.segf(self.data[R-1], x)
            if L & 1:
                self.data[L-1] = self.segf(self.data[L-1], x)
                L += 1
            L >>= 1
            R >>= 1
        
class Lazysegtree:
    def __init__(self, A):
        #区間は 1-indexed で管理
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv1 = inf
        self.intv2 = -inf
        self.segf1 = min
        self.segf2 = max
        self.lazy = [1]*(2*self.N0)
        self.data1 = [self.intv1]*self.N0 + A + [self.intv1]*(self.N0 - self.N)
        for i in range(self.N0-1, 0, -1):
            self.data1[i] = self.segf1(self.data1[2*i], self.data1[2*i+1]) 
        self.data2 = [self.intv2]*self.N0 + A + [self.intv2]*(self.N0 - self.N)
        for i in range(self.N0-1, 0, -1):
            self.data2[i] = self.segf2(self.data2[2*i], self.data2[2*i+1]) 
       
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data1[idx] = self.segf1(self.data1[2*idx], self.data1[2*idx+1])
            self.data2[idx] = self.segf2(self.data2[2*idx], self.data2[2*idx+1])
            
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            ax = self.lazy[idx]
            if ax == 1:
                continue
            self.lazy[idx] = 1
            self.data1[2*idx], self.data2[2*idx] = -self.data2[2*idx], -self.data1[2*idx]
            self.data1[2*idx+1], self.data2[2*idx+1] = -self.data2[2*idx+1], -self.data1[2*idx+1]
            self.lazy[2*idx] *= ax
            self.lazy[2*idx+1] *= ax
    
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri - 1)
        
        s1 = self.intv1
        s2 = self.intv2                                                              
        while L < R:
            if R & 1:
                R -= 1
                s1 = self.segf1(s1, self.data1[R])
                s2 = self.segf2(s2, self.data2[R])

            if L & 1:
                s1 = self.segf1(s1, self.data1[L])
                s2 = self.segf2(s2, self.data2[L])
                L += 1
            L >>= 1
            R >>= 1
        return (s1, s2)
    
    def update(self, i, x):
        idx = i+self.N0
        self.data1[idx] = x
        self.data2[idx] = x
        self._ascend(idx)
        
    def updaterange(self, l, r, x):
        L = l+self.N0
        R = r+self.N0

        Li = L//(L & -L)
        Ri = R//(R & -R)
        
        while L < R :
            if R & 1:
                R -= 1
                self.data1[R], self.data2[R] = -self.data2[R], -self.data1[R]
                self.lazy[R] *= x
            if L & 1:
                self.data1[L], self.data2[L] = -self.data2[L], -self.data1[L]
                self.lazy[L] *= x
                L += 1
            L >>= 1
            R >>= 1
        
        self._ascend(Li)
        self._ascend(Ri-1)

N = int(readline())

inf = 1<<32
P = list(map(int, readline().split()))

Pi = [None]*(N+1)
for i in range(N):
    Pi[P[i]] = i

T = Lazysegtree([(N+1 - P[i])*(-1)**i for i in range(N)])
N0 = 2**(N-1).bit_length()

R = Dualsegtree([N0]*N, N0, initialize = True)
for i in range(N//2):
    _, t2 = T.query(0, N0)
    t2 = N+1-abs(t2)
    p2 = Pi[t2]
    t1, _ = T.query(p2, R.query(p2))
    t1 = N+1-abs(t1)
    p1 = Pi[t1]
    
    if p1 > p2:
        p1, p2 = p2, p1
    T.update(p1, 0)
    T.update(p2, 0)
    T.updaterange(p1+1, p2, -1)
    R.update(0, p1, p1)
    R.update(0, p2, p2)
    
    sys.stdout.write('{} {} '.format(t2, t1))
sys.stdout.write('\n')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)
	adj[t-1].append(s-1)
par = [-1 for _ in range(n)]
aff = [0 for _ in range(n)]

def dfs(x, p):
	for v in adj[x]:
		if v == p:
			continue
		aff[x] += 1
		par[v] = x
		dfs(v, x)
	return
dfs(0, -1)
af_lis = [[] for _ in range(n)]
zero = [i for i in range(n) if aff[i] == 0]

def check(x):
	if af_lis[x] == []:
		af_lis[par[x]].append(a[x])
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	s, ma = sum(af_lis[x]), max(af_lis[x])
	if ma*2 > s:
		s_mi = ma
	else:
		s_mi = (s+1)//2
	if s_mi <= a[x] <= s:
		if par[x] == -1:
			if 2*a[x] != s:
				print("NO")
				sys.exit()
			else:
				return
		af_lis[par[x]].append(2*a[x] - s)
		aff[par[x]] -= 1
		if aff[par[x]] == 0:
			zero.append(par[x])
		return
	else:
		print("NO")
		sys.exit()
		return

while zero:
	check(zero.pop())

print("YES")

Submission status: Runtime Error

Solution code:
import numpy as np

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

def smallest_list(l,r): #P[l:r] r:exclusive
  if l == r or l+1 == r:
    return []
  if l+2 == r:
    return [(P[l],P[l+1])]
  
  i = l + 2*np.argmin(P[l:r:2])
  j = i+1 + 2*np.argmin(P[i+1:r:2])
  
  ans = [(P[i],P[j])]
  
  l1 = smallest_list(l,i) + [(1e9,1e9)]
  l2 = smallest_list(i+1,j) + [(1e9,1e9)]
  l3 = smallest_list(j+1,r) + [(1e9,1e9)]

  i1 = 0
  i2 = 0
  i3 = 0
  
  while i1<len(l1)-1 or i2<len(l2)-1 or i3<len(l3)-1:
    if l1[i1] < l2[i2] and l1[i1] < l3[i3]:
      ans.append(l1[i1])
      i1+=1
    elif l2[i2] < l3[i3]:
      ans.append(l2[i2])
      i2+=1
    else:
      ans.append(l3[i3])
      i3+=1
  return ans

print(' '.join([str(x) + ' ' + str(y) for x, y in smallest_list(0,N)]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

def smallest_list(Q):
  if len(Q) ==0:
    return []
  if len(Q) == 2:
    return [tuple(list(Q))]
  
  i = 2*np.argmin(Q[::2])
  #print(i, Q[::2])
  
  ans = [(Q[i],Q[-1])]
  
  f = smallest_list(Q[:i]) + [(1e9,1e9)]
  #print(f)
  s = smallest_list(Q[i+1:-1]) + [(1e9,1e9)]
  #print(s)
  fi = 0
  si = 0
  while fi <= len(f)-2 or si <= len(s)-2:
    if f[fi] < s[si]:
      ans.append(f[fi])
      fi += 1
    else:
      ans.append(s[si])
      si += 1
  return ans

print(' '.join([str(x) + ' ' + str(y) for x, y in smallest_list(P)]))

Submission status: Runtime Error

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-1+n] = 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)

N0 = N//2
def get(data, l, 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+1)//2, (r+1)//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: Runtime Error

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)
    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: Runtime Error

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 = [(*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: Runtime Error

Solution code:

from itertools import count,chain
from collections import deque
import heapq as hq
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))))


Q = [(0,0,N)]

ans = []

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

  if s%2 == 0:
    T1,T2 = Te,To
  else:
    T1,T2 = To,Te

  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:i][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: Runtime Error

Solution code:

from itertools import count,chain
from collections import deque

class MinSegTree:

  def __init__(self, constant, size):

    self.size = size
    self.depth = (size-1).bit_length()
    self.capacity = 1 << self.depth
    self.data = [constant]*(2*self.capacity)
    self.inf = constant

  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), N)
To = MinSegTree((N+1,N), N)

for i,p in enumerate(P):
  if i%2 == 0:
    Te[i] = (p,i)
  else:
    To[i] = (p,i)

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:t]
    p2,j = To[i+1:t]
  else:
    p1,i = To[s:t]
    p2,j = Te[i+1:t]

  # 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]

  return M

ans = rec(0,N)

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

Submission status: Runtime Error

Solution code:
n = input()
arr = map(int, raw_input().split())
idx = [0 for i in range(n)]
sec = [0 for i in range(n)]
for i in range(n):
	idx[arr[i] - 1] = i

result = []
while n > 0:
	i = 0
	while 1:
		if (idx[i] - sec[idx[i]]) % 2 == 0:
			target = idx.pop(i);
			break
		i += 1
	i = 0
	while 1:
		if sec[idx[i]] == sec[target] and (idx[i] - sec[idx[i]]) % 2 == 1:
			target2 = idx.pop(i);
			break
		i += 1

	i = target
	while i < target2:
		sec[i] += 1
		i += 1
	result.append(str(arr[target]))
	result.append(str(arr[target2]))
	n -= 2
print " ".join(result)

Submission status: Runtime Error

Solution code:
N=int(raw_input())
p=map(int,raw_input().split())
l=N/2
ps=[-1,N]
q=[]
while l:
    #1
    mm=N+1
    for i in range(len(ps)-1):
        m=min(p[ps[i]+1:ps[i+1]-1:2]+[N+1])
        if m<mm:
            mm=m
            j=i
    q.append(mm)
    i=p.index(mm)
    p[i]=N+1
    #2
    mm=min(p[i+1:ps[j+1]:2])
    q.append(mm)
    j=p.index(mm)
    p[j]=N+1
    ps=sorted(ps+[i,j])
    l-=1
print " ".join(map(str,q))