Import sys import random import heapq # Простая имплементация treap для множества целых ключей (позиции) class TreapNode: __slots__ = ('key', 'prio', 'left', 'right') def __init__(self, key): self.key = key self.prio = random.randint(1, 1 << 30) self.left = None self.right = None def rotate_right(root): L = root.left root.left = L.right L.right = root return L def rotate_left(root): R = root.right root.right = R.left R.left = root return R def insert(root, key): if root is None: return TreapNode(key) if key < root.key: root.left = insert(root.left, key) if root.left.prio < root.prio: root = rotate_right(root) elif key > root.key: root.right = insert(root.right, key) if root.right.prio < root.prio: root = rotate_left(root) # если key == root.key, ничего не делаем (уникальные позиции) return root def predecessor(root, key): # максимальное значение <= key, или None если такого нет res = None while root: if key == root.key: return key if key > root.key: res = root.key root = root.right else: root = root.left return res def successor(root, key): # минимальное значение >= key, или None res = None while root: if key == root.key: return key if key < root.key: res = root.key root = root.left else: root = root.right return res def dist_to_S(pos_t, root): # расстояние до ближайшей позиции из S p = predecessor(root, pos_t) s = successor(root, pos_t) d = 10**9 if p is not None: d = min(d, pos_t - p) if s is not None: d = min(d, s - pos_t) return d def main(): data = list(map(int, sys.stdin.buffer.read().split())) if not data: return N = data[0] A = data[1:1+N] # pos[value] = индекс в старом списке pos = {val: i for i, val in enumerate(A)} # первый элемент нового списка first = A[0] result = [first] random.seed(0xC0FFEE) # S = множество позиций выбранных номеров; начинаем с {0} root = None root = insert(root, 0) # Куча кандидатов: для каждого оставшегося элемента heap = [] for i in range(1, N): val = A[i] t = i # позиция этого элемента в старом списке dist = abs(t - 0) # расстояние до элемента на позиции 0 heapq.heappush(heap, (-dist, t, val)) while len(result) < N: negdist, t, val = heapq.heappop(heap) dcur = dist_to_S(t, root) dist_in_heap = -negdist if dcur != dist_in_heap: # обновляем расстояние в куче и продолжаем heapq.heappush(heap, (-dcur, t, val)) continue # принимаем текущий элемент result.append(val) root = insert(root, t) print(' '.join(map(str, result))) if __name__ == "__main__": # чтобы не было проблем с максимальной глубиной рекурсии sys.setrecursionlimit(1 << 25) main() на каком это языке програмиррвания