from heapq import heappush, heapify, heappop from itertools import pairwise import sys from bisect import bisect_left, bisect_right # https://github.com/tatyam-prime/SortedSet/blob/main/SortedSet.py import math from collections import defaultdict from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional, Hashable T = TypeVar('T') def printe(*args, end="\n", **kwargs): print(*args, end=end, file=sys.stderr, **kwargs) T_ = TypeVar('T_', bound=Hashable) class RemovableHeapQueue: def __init__(self, seq: list[T_] = None) -> None: self.__queue: list[T_] = [] if seq is not None: self.__queue.extend(seq) heapify(self.__queue) self.__remove_queue: dict[T_, int] = defaultdict(int) self.__length = len(self.__queue) def pop(self) -> T_: while self.__queue: value = heappop(self.__queue) if self.__remove_queue[value] > 0: self.__remove_queue[value] -= 1 continue self.__length -= 1 return value raise IndexError def push(self, item: T_) -> None: self.__length += 1 if self.__remove_queue[item] > 0: self.__remove_queue[item] -= 1 return heappush(self.__queue, item) @property def top(self) -> T_: while self.__queue: value = self.__queue[0] if self.__remove_queue[value] > 0: heappop(self.__queue) self.__remove_queue[value] -= 1 continue return value raise IndexError def remove(self, item: T_) -> None: self.__remove_queue[item] += 1 self.__length -= 1 def __len__(self) -> int: return self.__length def main(): N = int(input()) p = list(map(int, input().split())) next_idxs = list(range(1, N + 1)) next_idxs[-1] = -1 prev_idxs = list(range(-1, N - 1)) pairs_set = RemovableHeapQueue() for idx, (pair_1, pair_2) in enumerate(pairwise(p)): pairs_set.push((pair_1, pair_2, idx, idx + 1)) q = [] while pairs_set and len(q) < N: used = pairs_set.pop() q.extend(used[:2]) idx_1 = used[2] idx_2 = used[3] if prev_idxs[idx_1] != -1: pairs_set.remove( (p[prev_idxs[idx_1]], p[idx_1], prev_idxs[idx_1], idx_1)) if next_idxs[idx_2] != -1: pairs_set.remove( (p[idx_2], p[next_idxs[idx_2]], idx_2, next_idxs[idx_2])) if prev_idxs[idx_1] != -1 and next_idxs[idx_2] != -1: pairs_set.push((p[prev_idxs[idx_1]], p[next_idxs[idx_2]], prev_idxs[idx_1], next_idxs[idx_2])) # 前後関係を更新する if prev_idxs[idx_1] != -1: if next_idxs[idx_2] != -1: next_idxs[prev_idxs[idx_1]] = next_idxs[idx_2] else: next_idxs[prev_idxs[idx_1]] = -1 if next_idxs[idx_2] != -1: if prev_idxs[idx_1] != -1: prev_idxs[next_idxs[idx_2]] = prev_idxs[idx_1] else: prev_idxs[next_idxs[idx_2]] = -1 print(*q) if __name__ == "__main__": main()