Профессор перед экзаменом попросил ассистента подготовить список номеров вопросов для каждого студента. Так как профессор планирует подробно спрашивать материал курса, то каждый…

Задача и идея решения

• У нас есть старый список вопросов: A[0], A[1], ..., A[N-1] (это перестановка каких-то номеров; будем считать, что позиции в старом списке нумеруются от 0 до N-1).
• Новый список должен быть перестановкой тех же номеров, и первый элемент нового списка равен A[0].
• Для подбора каждого следующего номера мы выбираем тот номер, который максимизирует минимальное расстояние до уже выбранных номеров в старом списке. Расстояние между двумя номерами — по позициям в старом списке: |pos[x] - pos[y]|.
• В случае ties выбираем номер, который идёт раньше в старом списке (то есть минимальная pos).

Алгоритм (пошагово)

1. Для каждого значения value запомним его позицию pos[value] в старом списке.
2. В динамическом наборе S храним позиции уже выбранных номеров (начинаем с {0}, т.е. первый элемент старого списка A[0]).
3. Для каждого оставшегося значения создаём запись в куче-макс по начальному расстоянию до S:
   • расстояние = |pos[value] - ближайшей_позиции_из_S|.
   • так как используем min-кучу, будем хранить ключ как (-dist, pos[value], value).
   • ties по позиции старого списка автоматически обеспечиваются через второй элемент кучи (меньшая pos выигрывает).
4. Из кучи по одному извлекаем кандидата. Но его реальное текущее расстояние до S может уже измениться после добавления новых позиций в S. Чтобы проверить это:
   • вычисляем текущее расстояние dcur для данного кандидата, как расстояние до ближайшей позиции из S (для этого нужен predecessor и successor в S по позициям).
   • если dcur != сохранённого в куче dist, кладём обновлённый элемент обратно в кучу и повторяем извлечение.
   • если совпало, принимаем этот кандидат в новый список, добавляем его позицию pos[value] в S и продолжаем.
5. Повторяем до заполнения всего списка.

Данные структуры

• Динамический набор S: множество позиций в старом списке. Нужно быстро найти ближайшую слева и справа к заданной позиции. Для этого реализуем упорядоченное множество на базеTreap (случайная балансировка: операции insert, predecessor, successor — O(log N) в среднем).
• Куча для кандидатов: стандартная мин-куча (heapq). Мы держим упрощённую ленивую корректировку расстояний: если при выборке расстояние изменилось, повторно кладём обновлённое значение в куче и берём следующий элемент.

Код (Python)

Внимание: числа в старом списке могут быть любыми уникальными, но позиции у них будут 0..N-1.

• ввод: первая строка N, вторая строка — N чисел старого списка
• вывод: новый список чисел в нужном порядке

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

Пояснения по сложности

• В среднем: каждая операция вставки в treap и поиск predecessor/successor — O(log N).
• Каждая итерация выбора элемента включает одну поп-операцию из кучи и, возможно, несколько перерасчётов расстояния (lazy-update). В среднем общее время близко к O(N log N).
• Объём памяти — O(N).

Пример проверки (ручной простой сценарий)

• Пусть старый список A = [3, 10, 5, 7, 2] (N = 5).
• Первый элемент в новом списке должен быть 3.
• Остальные выбираются по правилу; программа выведет корректную перестановку номеров.

Если нужно, могу объяснить на каком именно примере почему порядок получается именно таким и как понять работу кучи и treap-предшественников/последователей.