AtCoder Regular Contest 080 - Young Maids

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-----
4
3 2 4 1

-----Sample Output-----
3 1 2 4

The solution above is obtained as follows:pq(3, 2, 4, 1)()↓↓(3, 1)(2, 4)↓↓()(3, 1, 2, 4)

Source: atcoder | Difficulty: VERY_HARD


Solutions:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
N = int(input())
A = [int(x) for x in input().split()]
a_to_i = {a: i for (i, a) in enumerate(A)}
U = len(A).bit_length()
sp = [None, A]
for i in range(2, U):
	L = 1 << i - 1
	sp.append([x if x < y else y for (x, y) in zip(sp[-1][:-L], sp[-1][L:])])

def RMQ(x, y):
	d = y - x
	if d <= 1:
		return A[x]
	n = d.bit_length()
	return min(sp[n - 1][x], sp[n - 1][y + 2 - (1 << n - 1)])

def F(x, y):
	x1 = RMQ(x, y - 1)
	i1 = a_to_i[x1]
	x2 = RMQ(i1 + 1, y)
	i2 = a_to_i[x2]
	task = ((x, y) for (x, y) in ((x, i1 - 1), (i1 + 1, i2 - 1), (i2 + 1, y)) if y > x)
	return (x1, x2, task)
q = [(None, None, ((0, N - 1),))]
answer = []
while q:
	(x, y, task) = heappop(q)
	answer.append(x)
	answer.append(y)
	for (left, right) in task:
		heappush(q, F(left, right))
print(' '.join(map(str, answer[2:])))


N = int(input())
(*P,) = map(int, input().split())
M = [0] * (N + 1)
from heapq import heappush, heappop
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(data, l, r):
	n0 = len(data) // 2
	l += n0
	r += n0
	while l < r:
		if r & 1:
			r -= 1
			yield data[r - 1]
		if l & 1:
			yield data[l - 1]
			l += 1
		l >>= 1
		r >>= 1

def get(data, l, r):
	return min(get_data(data, l, r))
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
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]
		if l < xi:
			heappush(que, (query_x(l, xi), l, xi))
		if xi + 1 < yi:
			heappush(que, (query_x(xi + 1, yi), xi + 1, yi))
		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)


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)
		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)
		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)
	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)))


import sys
input = sys.stdin.buffer.readline

class SparseTable:

	def __init__(self, N, A):
		self.N = N
		self.logN = N.bit_length()
		self.A = A
		self.table = [[i for i in range(N)]]
		for k in range(self.logN):
			tab = []
			for i in range(self.N - (1 << k + 1) + 1):
				ind1 = self.table[-1][i]
				ind2 = self.table[-1][i + (1 << k)]
				if self.A[ind1] <= self.A[ind2]:
					tab.append(ind1)
				else:
					tab.append(ind2)
			self.table.append(tab)

	def query_min(self, l, r):
		k = (r - l).bit_length() - 1
		indl = self.table[k][l]
		indr = self.table[k][r - (1 << k)]
		if self.A[indl] <= self.A[indr]:
			return (self.A[indl], indl)
		return (self.A[indr], indr)
import heapq as hp
N = int(input())
A = list(map(int, input().split()))

def main():
	SP1 = SparseTable((N + 1) // 2, A[::2])
	SP2 = SparseTable(N // 2, A[1::2])
	ans = []
	q = []
	(v, k) = SP1.query_min(0, N // 2)
	dic = {}
	dic[v] = (k, 0, N // 2, True)
	hp.heappush(q, v)
	for _ in range(N // 2):
		valuea = hp.heappop(q)
		(ka, l, r, is1) = dic[valuea]
		ans.append(str(valuea))
		if is1:
			(valueb, kb) = SP2.query_min(ka, r)
			if ka < kb:
				(m2, nk2) = SP2.query_min(ka, kb)
				hp.heappush(q, m2)
				dic[m2] = (nk2, ka, kb + 1, False)
			if l < ka:
				(m1, nk1) = SP1.query_min(l, ka)
				hp.heappush(q, m1)
				dic[m1] = (nk1, l, ka, True)
			if kb + 1 < r:
				(m3, nk3) = SP1.query_min(kb + 1, r)
				hp.heappush(q, m3)
				dic[m3] = (nk3, kb + 1, r, True)
		else:
			(valueb, kb) = SP1.query_min(ka + 1, r)
			if ka + 1 < kb:
				(m1, nk1) = SP1.query_min(ka + 1, kb)
				hp.heappush(q, m1)
				dic[m1] = (nk1, ka + 1, kb, True)
			if l < ka:
				(m2, nk2) = SP2.query_min(l, ka)
				hp.heappush(q, m2)
				dic[m2] = (nk2, l, ka + 1, False)
			if kb < r - 1:
				(m3, nk3) = SP2.query_min(kb, r - 1)
				hp.heappush(q, m3)
				dic[m3] = (nk3, kb, r, False)
		ans.append(str(valueb))
	print(' '.join(ans))
main()


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)

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

	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

	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):
		return self.dat[k + self.N0]
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)
	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)


from sys import stdin
import heapq

def make_ST(n, first):
	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):
	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):
	if r <= a or b <= l:
		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)
	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)


import sys
from heapq import heappop, heappush

class SegTreeMin:

	def __init__(self, n, INF):
		n2 = 1 << (n - 1).bit_length()
		self.offset = n2
		self.tree = [INF] * (n2 << 1)
		self.INF = INF

	@classmethod
	def from_array(cls, arr, INF):
		ins = cls(len(arr), INF)
		ins.tree[ins.offset:ins.offset + len(arr)] = arr
		for i in range(ins.offset - 1, 0, -1):
			l = i << 1
			r = l + 1
			ins.tree[i] = min(ins.tree[l], ins.tree[r])
		return ins

	def update(self, i, x):
		i += self.offset
		self.tree[i] = x
		while i > 1:
			y = self.tree[i ^ 1]
			if y <= x:
				break
			i >>= 1
			self.tree[i] = x

	def get_min(self, a, b):
		result = self.INF
		l = a + self.offset
		r = b + self.offset
		while l < r:
			if r & 1:
				result = min(result, self.tree[r - 1])
			if l & 1:
				result = min(result, self.tree[l])
				l += 1
			l >>= 1
			r >>= 1
		return result
(n, *ppp) = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18
indices = [0] * (n + 1)
even_p = [INF] * n
odd_p = [INF] * n
for (i, p) in enumerate(ppp):
	indices[p] = i
	if i % 2 == 0:
		even_p[i] = p
	else:
		odd_p[i] = p
sgt0 = SegTreeMin.from_array(even_p, INF)
sgt1 = SegTreeMin.from_array(odd_p, INF)
sgt = [sgt0, sgt1]
ans = []
heap = []
data = {}
first_p = sgt0.get_min(0, n)
i = indices[first_p]
first_q = sgt1.get_min(i, n)
j = indices[first_q]
heap.append(first_p)
data[first_p] = (first_q, 0, n, i, j)
while heap:
	p = heappop(heap)
	(q, l, r, i, j) = data.pop(p)
	ans.append(p)
	ans.append(q)
	if l < i:
		k = l % 2
		np = sgt[k].get_min(l, i)
		ni = indices[np]
		nq = sgt[k ^ 1].get_min(ni, i)
		nj = indices[nq]
		heappush(heap, np)
		data[np] = (nq, l, i, ni, nj)
	if i + 1 < j:
		k = (i + 1) % 2
		np = sgt[k].get_min(i + 1, j)
		ni = indices[np]
		nq = sgt[k ^ 1].get_min(ni, j)
		nj = indices[nq]
		heappush(heap, np)
		data[np] = (nq, i + 1, j, ni, nj)
	if j + 1 < r:
		k = (j + 1) % 2
		np = sgt[k].get_min(j + 1, r)
		ni = indices[np]
		nq = sgt[k ^ 1].get_min(ni, r)
		nj = indices[nq]
		heappush(heap, np)
		data[np] = (nq, j + 1, r, ni, nj)
print(*ans)


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

class SegmentTree:

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


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 SparseTable:

	def __init__(self, aa):
		inf = 10 ** 16
		w = len(aa)
		h = w.bit_length()
		table = [aa] * 2 + [[inf] * w for _ in range(h - 2)]
		tablei1 = table[0]
		for i in range(2, h):
			tablei = table[i]
			shift = 1 << i - 1
			for j in range(w):
				rj = j + shift
				if rj >= w:
					break
				tablei[j] = min(tablei1[j], tablei1[rj])
			tablei1 = tablei
		self.table = table

	def min(self, l, r):
		if (r - l) % 2:
			r += 1
		i = (r - l).bit_length() - 1
		tablei = self.table[i]
		Lmin = tablei[l]
		Rmin = tablei[r - (1 << i)]
		if Lmin < Rmin:
			Rmin = Lmin
		return Rmin

def main():
	n = int(input())
	pp = LI()
	st = SparseTable(pp)
	ptoi = [0] + [i for (i, p) in sorted(enumerate(pp), key=lambda x: x[1])]
	hp = []
	heappush(hp, [st.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]
		y = st.min(xi + 1, r)
		yi = ptoi[y]
		if xi > l:
			heappush(hp, [st.min(l, xi), l, xi])
		if xi + 1 < yi:
			heappush(hp, [st.min(xi + 1, yi), xi + 1, yi])
		if yi < r - 1:
			heappush(hp, [st.min(yi + 1, r), yi + 1, r])
		ans += [x, y]
	print(*ans)
main()


def main():
	import sys
	from heapq import heappush, heappop
	input = sys.stdin.buffer.readline

	def STfunc(a, b):
		if a < b:
			return a
		else:
			return b

	class SparseTable:

		def __init__(self, A):
			self.N = len(A)
			self.K = self.N.bit_length() - 1
			self.table = [[0] * (self.K + 1) for _ in range(self.N)]
			for (i, a) in enumerate(A):
				self.table[i][0] = A[i]
			for k in range(1, self.K + 1):
				for i in range(self.N):
					j = i + (1 << k - 1)
					if j <= self.N - 1:
						self.table[i][k] = STfunc(self.table[i][k - 1], self.table[j][k - 1])
					else:
						self.table[i][k] = self.table[i][k - 1]

		def query(self, l, r):
			k = (r - l).bit_length() - 1
			return STfunc(self.table[l][k], self.table[r - (1 << k)][k])
	N = int(input())
	n = N // 2
	A = list(map(int, input().split()))
	A_even = A[0:N:2]
	A_odd = A[1:N:2]
	ST_even = SparseTable(A_even)
	ST_odd = SparseTable(A_odd)
	val2idx = [0] * (N + 1)
	for i in range(N):
		val2idx[A[i]] = i
	ans = []
	ans_append = ans.append
	pq = [(ST_even.query(0, n), 0, N)]
	for t in range(n):
		(v1, left, right) = heappop(pq)
		ans_append(v1)
		i = val2idx[v1]
		if i & 1:
			v2 = ST_even.query((i + 1) // 2, right // 2 + 1)
			ans_append(v2)
			j = val2idx[v2]
			if left != i:
				heappush(pq, (ST_odd.query(left // 2, i // 2), left, i))
			if j - i > 1:
				heappush(pq, (ST_even.query((i + 1) // 2, j // 2), i + 1, j))
			if j + 1 != right:
				heappush(pq, (ST_odd.query((j + 1) // 2, right // 2), j + 1, right))
		else:
			v2 = ST_odd.query(i // 2, right // 2)
			ans_append(v2)
			j = val2idx[v2]
			if left != i:
				heappush(pq, (ST_even.query(left // 2, i // 2), left, i))
			if j - i > 1:
				heappush(pq, (ST_odd.query((i + 1) // 2, j // 2), i + 1, j))
			if j + 1 != right:
				heappush(pq, (ST_even.query((j + 1) // 2, right // 2), j + 1, right))
	print(*ans)
main()


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(p1, r)
		p2 = Pi[t2]
		Teven.update(p1, inf)
		Todd.update(p2, inf)
	else:
		p1 = Pi[t1]
		t2 = Teven.query(p1, 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')


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 = 1 << 32

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, segfunc, initialize=True):
		self.n = len(A)
		self.size = 2 ** (self.n - 1).bit_length()
		self.ide_ele = ide_ele
		self.segfunc = segfunc
		if initialize:
			self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
			for i in range(self.size - 1, 0, -1):
				self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])
		else:
			self.data = [ide_ele] * (2 * self.size)

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

	def query(self, l, r):
		(L, R) = (l + self.size, r + self.size)
		s = self.ide_ele
		while L < R:
			if R & 1:
				R -= 1
				s = self.segfunc(s, self.data[R])
			if L & 1:
				s = self.segfunc(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 & 1 else INF for i in range(n)]
p_odd = [P[i] if i & 1 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 _ 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)


class SegTree:

	def __init__(self, init_val, ide_ele, segfunc):
		self.n = len(init_val)
		self.num = 2 ** (self.n - 1).bit_length()
		self.ide_ele = ide_ele
		self.seg = [self.ide_ele] * 2 * self.num
		self.segfunc = segfunc
		for i in range(self.n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

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

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	P = list(map(int, input().split()))
	Even = []
	Odd = []
	D = {}
	for i in range(N // 2):
		e = P[2 * i]
		o = P[2 * i + 1]
		D[e] = i
		D[o] = i
		Even.append(e)
		Odd.append(o)
	E_Seg = SegTree(Even, float('inf'), min)
	O_Seg = SegTree(Odd, float('inf'), min)
	import heapq
	heap = []

	def BFS(H):
		L = H[0]
		R = H[1]
		if R <= L:
			return (-1, -1, -1, -1, -1)
		if L % 2 == 0:
			l = L // 2
			r = R // 2
			mini = E_Seg.query(l, r + 1)
			d_mini = D[mini]
			mini_b = O_Seg.query(d_mini, r + 1)
			d_mini_b = D[mini_b]
			leftH = (L, 2 * d_mini - 1)
			centH = (2 * d_mini + 1, 2 * d_mini_b)
			rightH = (2 * d_mini_b + 2, R)
			return (mini, mini_b, leftH, centH, rightH)
		else:
			l = L // 2
			r = R // 2
			mini = O_Seg.query(l, r)
			d_mini = D[mini]
			mini_b = E_Seg.query(d_mini + 1, r + 1)
			d_mini_b = D[mini_b]
			leftH = (L, 2 * d_mini)
			centH = (2 * d_mini + 2, 2 * d_mini_b - 1)
			rightH = (2 * d_mini_b + 1, R)
			return (mini, mini_b, leftH, centH, rightH)
	H = (0, N - 1)
	(m1, m2, LH, CH, RH) = BFS(H)
	heapq.heappush(heap, [m1, m2, LH, CH, RH])
	Q = []
	while heap != []:
		(m1, m2, LH, CH, RH) = heapq.heappop(heap)
		Q += [m1, m2]
		(m1L, m2L, LHL, CHL, RHL) = BFS(LH)
		if m1L != -1:
			heapq.heappush(heap, [m1L, m2L, LHL, CHL, RHL])
		(m1C, m2C, LHC, CHC, RHC) = BFS(CH)
		if m1C != -1:
			heapq.heappush(heap, [m1C, m2C, LHC, CHC, RHC])
		(m1R, m2R, LHR, CHR, RHR) = BFS(RH)
		if m1R != -1:
			heapq.heappush(heap, [m1R, m2R, LHR, CHR, RHR])
	print(*Q)
main()


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())


import heapq
import sys
input = sys.stdin.readline

class SegmentTreeMin:

	def __init__(self, n, init):
		self.offset = 2 ** (n - 1).bit_length()
		self.tree = [init] * (2 * self.offset)
		self.init = init

	def update(self, pos, val):
		pos += self.offset
		self.tree[pos] = val
		while pos > 1:
			pos = pos // 2
			self.tree[pos] = min(self.tree[2 * pos], self.tree[2 * pos + 1])

	def query(self, l, r):
		l += self.offset
		r += self.offset
		ret = self.init
		while l <= r:
			ret = min(ret, self.tree[r])
			r = (r - 1) // 2
			ret = min(ret, self.tree[l])
			l = (l + 1) // 2
		return ret
n = int(input())
arr = list(map(int, input().split()))
odds = SegmentTreeMin(n // 2, 10 ** 18)
evens = SegmentTreeMin(n // 2, 10 ** 18)
dic = {}
for i in range(n):
	dic[arr[i]] = i
	if i % 2 == 0:
		odds.update(i // 2, arr[i])
	else:
		evens.update(i // 2, arr[i])
q = []
heapq.heappush(q, (odds.query(0, (n - 1) // 2), 0, n - 1))
ans = []
while len(q) != 0:
	(_, l, r) = heapq.heappop(q)
	if l % 2 == 0:
		a = odds.query(l // 2, r // 2)
		odds.update(dic[a] // 2, 10 ** 18)
		b = evens.query(dic[a] // 2, r // 2)
		evens.update(dic[b] // 2, 10 ** 18)
		ans.append(a)
		ans.append(b)
		tl = dic[a]
		tr = dic[b]
		if tl != l:
			heapq.heappush(q, (odds.query(l // 2, (tl - 1) // 2), l, tl - 1))
		if tl + 1 < tr - 1:
			heapq.heappush(q, (evens.query((tl + 1) // 2, (tr - 1) // 2), tl + 1, tr - 1))
		if tr != r:
			heapq.heappush(q, (odds.query((tr + 1) // 2, r // 2), tr + 1, r))
	else:
		a = evens.query(l // 2, r // 2)
		evens.update(dic[a] // 2, 10 ** 18)
		b = odds.query((dic[a] + 1) // 2, r // 2)
		odds.update(dic[b] // 2, 10 ** 18)
		ans.append(a)
		ans.append(b)
		tl = dic[a]
		tr = dic[b]
		if tl != l:
			heapq.heappush(q, (evens.query(l // 2, (tl - 1) // 2), l, tl - 1))
		if tl + 1 < tr - 1:
			heapq.heappush(q, (odds.query((tl + 1) // 2, (tr - 1) // 2), tl + 1, tr - 1))
		if tr != r:
			heapq.heappush(q, (evens.query((tr + 1) // 2, r // 2), tr + 1, r))
print(*ans)


from collections import deque
import heapq
import sys
input = sys.stdin.readline

class SparseTable:

	def __init__(self, array, n):
		n = len(array)
		self.row_size = n.bit_length()
		self.log_table = [0] * (n + 1)
		for i in range(2, n + 1):
			self.log_table[i] = self.log_table[i // 2] + 1
		self.sparse_table = [[0] * n for _ in range(self.row_size)]
		for i in range(n):
			self.sparse_table[0][i] = array[i]
		for row in range(1, self.row_size):
			for i in range(n - (1 << row) + 1):
				self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], self.sparse_table[row - 1][i + (1 << row - 1)])

	def _merge(self, num1, num2):
		return min(num1, num2)

	def query(self, l, r):
		row = self.log_table[r - l]
		return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
n = int(input())
p = list(map(int, input().split()))
q = [[0] * (n // 2) for i in range(2)]
for i in range(n):
	q[i % 2][i // 2] = p[i]
ind = {}
for i in range(n):
	ind[p[i]] = i
sp0 = SparseTable(q[0], n // 2)
sp1 = SparseTable(q[1], n // 2)
con = {}
ans = {}
div = 10 ** 6

def solve(l, r):
	q = deque([l * div + r])
	while q:
		pos = q.pop()
		(l, r) = (pos // div, pos % div)
		if l % 2 == 0:
			min1 = sp0.query(l // 2, r // 2)
		else:
			min1 = sp1.query(l // 2, r // 2)
		use_pos1 = ind[min1]
		if (l + 1) % 2 == 0:
			min2 = sp0.query((use_pos1 + 1) // 2, (r + 1) // 2)
		else:
			min2 = sp1.query((use_pos1 + 1) // 2, (r + 1) // 2)
		use_pos2 = ind[min2]
		ans[pos] = min1 * div + min2
		con[pos] = []
		if l != use_pos1:
			con[pos].append(l * div + use_pos1)
			q.append(l * div + use_pos1)
		if use_pos1 + 1 != use_pos2:
			con[pos].append((use_pos1 + 1) * div + use_pos2)
			q.append((use_pos1 + 1) * div + use_pos2)
		if use_pos2 + 1 != r:
			con[pos].append((use_pos2 + 1) * div + r)
			q.append((use_pos2 + 1) * div + r)
	return
solve(0, n)
res = []
q = [(ans[n], n)]
while q:
	(num, i) = heapq.heappop(q)
	(min1, min2) = (num // div, num % div)
	res.append(min1)
	res.append(min2)
	for new_num in con[i]:
		heapq.heappush(q, (ans[new_num], new_num))
print(*res)


from heapq import heappop, heappush
INF = 10 ** 30

class Rmin:

	def __init__(self, size):
		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

	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)


def segfunc(x, y):
	if y[0] > x[0]:
		return x
	else:
		return y
ide_ele = (float('inf'), -1)

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res
import heapq
N = int(input())
p = list(map(int, input().split()))
n = N // 2
op = [(p[2 * i + 1], 2 * i + 1) for i in range(n)]
ep = [(p[2 * i], 2 * i) for i in range(n)]
oseg = SegTree(op, segfunc, ide_ele)
eseg = SegTree(ep, segfunc, ide_ele)

def first(l, r):
	if l >= r:
		return (-1, -1, -1, -1)
	if l % 2 == 0:
		(val, index) = eseg.query(l // 2, r // 2)
		(val2, index2) = oseg.query(index // 2, r // 2)
		return (val, val2, index, index2)
	else:
		(val, index) = oseg.query(l // 2, r // 2)
		(val2, index2) = eseg.query(index // 2 + 1, r // 2 + 1)
		return (val, val2, index, index2)
(val, val2, index, index2) = first(0, N)
que = [((val, val2), 0, N)]
heapq.heapify(que)
ans = []
while que:
	(tuple, l, r) = heapq.heappop(que)
	ans.append(tuple[0])
	ans.append(tuple[1])
	(val, val2, index, index2) = first(l, r)
	(val, val2, l1, r1) = first(l, index)
	if val != -1:
		heapq.heappush(que, ((val, val2), l, index))
	(val, val2, l2, r2) = first(index + 1, index2)
	if val != -1:
		heapq.heappush(que, ((val, val2), index + 1, index2))
	(val, val2, l3, r3) = first(index2 + 1, r)
	if val != -1:
		heapq.heappush(que, ((val, val2), index2 + 1, r))
print(*ans)


def main():
	n = int(input())
	p = list(map(lambda x: int(x) - 1, input().split()))
	pos = [j for (i, j) in sorted([(j, i) for (i, j) in enumerate(p)])]
	basesize = n >> 1
	num = 1
	while num < basesize:
		num *= 2
	num -= 1
	tree_even = [100001] * (num * 2 + 1)
	tree_odd = [100001] * (num * 2 + 1)
	for i in range(num, num + basesize):
		tree_even[i] = p[(i - num) * 2]
	for i in range(num - 1, -1, -1):
		tree_even[i] = min(tree_even[2 * i + 1:2 * i + 3])
	for i in range(num, num + basesize):
		tree_odd[i] = p[(i - num) * 2 + 1]
	for i in range(num - 1, -1, -1):
		tree_odd[i] = min(tree_odd[2 * i + 1:2 * i + 3])
	g = dict()
	d = dict()
	q = [n - 1]
	(qap, qp) = (q.append, q.pop)
	while q:
		t = qp()
		(m, M) = (t // n, t % n)
		if m + 1 == M:
			d[t] = p[m] * n + p[M]
			continue
		g[t] = []
		gap = g[t].append
		if m % 2 == 0:
			(i1, j1) = (m >> 1, (M >> 1) + 1)
			even = 200000
			(l, r) = (i1 + num, j1 + num)
			while l < r:
				if r % 2 == 0:
					r -= 1
					even = min(even, tree_even[r])
				if l % 2 == 0:
					even = min(even, tree_even[l])
					l += 1
				l >>= 1
				r >>= 1
			even_idx = pos[even]
			odd = 200000
			(l, r) = ((even_idx >> 1) + num, j1 + num)
			while l < r:
				if r % 2 == 0:
					r -= 1
					odd = min(odd, tree_odd[r])
				if l % 2 == 0:
					odd = min(odd, tree_odd[l])
					l += 1
				l >>= 1
				r >>= 1
			odd_idx = pos[odd]
			d[t] = even * n + odd
			if m != even_idx:
				s = m * n + even_idx - 1
				qap(s)
				gap(s)
			if M != odd_idx:
				s = (odd_idx + 1) * n + M
				qap(s)
				gap(s)
			if even_idx + 1 != odd_idx:
				s = (even_idx + 1) * n + odd_idx - 1
				qap(s)
				gap(s)
		else:
			(i1, j1) = (m >> 1, M >> 1)
			odd = 200000
			(l, r) = (i1 + num, j1 + num)
			while l < r:
				if r % 2 == 0:
					r -= 1
					odd = min(odd, tree_odd[r])
				if l % 2 == 0:
					odd = min(odd, tree_odd[l])
					l += 1
				l >>= 1
				r >>= 1
			odd_idx = pos[odd]
			even = 200000
			(l, r) = ((odd_idx >> 1) + 1 + num, j1 + 1 + num)
			while l < r:
				if r % 2 == 0:
					r -= 1
					even = min(even, tree_even[r])
				if l % 2 == 0:
					even = min(even, tree_even[l])
					l += 1
				l >>= 1
				r >>= 1
			even_idx = pos[even]
			d[t] = odd * n + even
			if m != odd_idx:
				s = m * n + odd_idx - 1
				qap(s)
				gap(s)
			if M != even_idx:
				s = (even_idx + 1) * n + M
				qap(s)
				gap(s)
			if odd_idx + 1 != even_idx:
				s = (odd_idx + 1) * n + even_idx - 1
				qap(s)
				gap(s)
	g2 = dict()
	for (i, t) in g.items():
		k = d[i]
		g2[k] = []
		ga = g2[k].append
		for j in t:
			ga(d[j])
	import heapq
	h = [d[n - 1]]
	heapq.heapify(h)
	ans = []
	hpop = heapq.heappop
	hpush = heapq.heappush
	while h:
		t = hpop(h)
		ans += [t // n + 1, t % n + 1]
		if t in g2:
			for s in g2[t]:
				hpush(h, s)
	print(*ans)
main()