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

Задача в отпуске: дан массив A из N чисел (перестановка из 1..N) — старый список номеров вопросов в порядке старта. Нужно построить новый список B по правилу:

• B[0] = A[0] (первый номер совпадает с первым в старом списке).
• Далее выбираем номера так, чтобы каждый новый элемент максимально отдалялся по позициям в старом списке от уже выбранных. Расстояние измеряется как минимальное расстояние по индексам между новым и любым уже выбранным индексом.
• Если таких номеров несколько, выбираем тот, который встречается раньше в старом списке.

Делаем это за O(N log N) за счет разбиения отрезков (глобальная идея ниже).

Пояснение идеи (пошагово, понятно даже школьнику)

• Пусть мы уже выбрали некоторый набор позиций S в старом списке. Между соседними выбранными позициями образуются «пустые» отрезки (граня) между ними. В пределах каждогоSuch отрезка можно выбрать кандидат pos так, чтобы минимальное расстояние до S было максимально возможным внутри этого отрезка.
• Для отрезка между двумя соседними выбранными индексами L и R (L < R) максимальное MinDist внутри этого отрезка равно floor((R - L) / 2). А сами кандидаты, достигающие этого, расположены в середине отрезка:
  • если R - L чётно: единственный середина pos = L + (R - L) / 2;
  • если R - L нечётно: две середины, но выбирается та с меньшим индексом (она же встречается раньше в старом списке).
• Поэтому эффективный метод: держим в приоритетной очереди все currently существующие границы (граня) между соседними выбранными позициями. Для каждого грани (L, R) кампания кандидата — это pos = L + floor((R - L) / 2) и dist = floor((R - L) / 2).
  • Сначала у нас выбрано только A[0]. Затем явно возьмём A[N-1] (это следующий кандидат по правилу: максимальное расстояние до 0 — это N-1).
  • После этого между выбранными позициями 0 и N-1 образуется грань (0, N-1). В неё помещаем её середину и далее будем делить грани, добавляя новые грани после каждого выбора.
• Тот кандидат, который в данный момент имеет максимальное dist; если нескольких — выбираем меньший pos (раньше в старом списке). Это естественно реализуется через приоритетную очередь, сортировку по (dist убыв., pos возрастан.).

Алгоритм

1. B[0] = A[0]. Пометим позицию 0 как выбранную.
2. Если N >= 2, B[1] = A[N-1]. Пометим позицию N-1 как выбранную.
3. Если между 0 и N-1 есть хотя бы одна невыбранная позиция (то есть N > 2), добавим грань (0, N-1) в приоритетную очередь:
   • dist = floor((N-1 - 0) / 2)
   • pos = 0 + dist
   • сохраняем грань как (L=0, R=N-1, pos)
   • в очереди упорядочиваем по (dist по убыв., pos по возрастанию)
4. Пока не заполнен весь список (пока не выписано N чисел):
   • берём грань с максимальным dist и меньшим pos (по сути — извлекаем верхушку кучи по условию).
   • выбираем pos как следующий элемент: B[k] = A[pos].
   • пометим pos как выбранный и удаляем этот грань.
   • разделяем грань на две новые: (L, pos) и (pos, R). Для каждой из них, если внутри есть невыбранные индексы, добавляем в очередь новый кандидат с:
     • dist' = floor((pos - L) / 2) для левой грани, pos' = L + dist'
     • dist'' = floor((R - pos) / 2) для правой грани, pos'' = pos + dist''
5. Повторяем до заполнения N элементов.

Сложность: каждое добавление/извлечение из очереди стоит O(log N). Всего добавляется не более N граней, итого O(N log N). Поскольку N ≤ 1e5, это нормально.

Пример проверки (наглядно):

• Пусть A = [1,2,3,4,5], N = 5.
  • B[0] = 1, B[1] = 5.
  • Грань (0,4): dist=2, pos=2.
  • Выбираем pos=2 → B[2] = 3.
  • Разделяем на (0,2) и (2,4). Их dist = 1, pos=1 и pos=3 соответственно.
  • Выбираем меньший pos среди тех с dist=1 → pos=1 → B[3] = 2.
  • Остался грань (2,4) с pos=3 → B[4] = 4. Итог: [1,5,3,2,4], что соответствует правилу.

Код на Python (быстрая реализация с приоритетной очередью)

import sys
import heapq

def solve():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    A = [next(it) for _ in range(N)]

    B = [0] * N
    chosen = [False] * N

    # Шаг 1: берем первый элемент
    B[0] = A[0]
    chosen[0] = True

    idx = 1
    # Шаг 2: если есть второй элемент, берем последний
    if N >= 2:
        B[1] = A[N - 1]
        chosen[N - 1] = True
        idx = 2

        # Шаг 3: если есть внутри грань, добавляем её в очередь
        heap = []
        if N - 1 - 0 > 1:  # есть хотя бы один элемент между 0 и N-1
            dist = (N - 1 - 0) // 2
            pos = 0 + dist
            heapq.heappush(heap, (-dist, pos, 0, N - 1))

        # Шаг 4: далее выбираем по правилу
        while idx < N and heap:
            negdist, pos, L, R = heapq.heappop(heap)
            dist = -negdist

            if chosen[pos]:
                continue  # если уже выбрали по каким-то причинам

            B[idx] = A[pos]
            chosen[pos] = True
            idx += 1

            # левая грань (L, pos)
            if pos - L > 1:
                d = (pos - L) // 2
                mid = L + d
                heapq.heappush(heap, (-d, mid, L, pos))

            # правая грань (pos, R)
            if R - pos > 1:
                d = (R - pos) // 2
                mid = pos + d
                heapq.heappush(heap, (-d, mid, pos, R))

    print(' '.join(map(str, B)))

if __name__ == "__main__":
    solve()

Пояснение к коду

• Первая и вторая выдачи (B[0] = A[0], B[1] = A[N-1]) реализуют начальные условия: первый номер совпадает с первым в старом списке, затем берётся самый дальний по индексу элемент.
• Дальше мы храним грани между уже выбранными индексами в приоритетной очереди, сортируемой по (dist убыв., pos возрастание), чтобы выбирать в случае равных dist тот кандидат, который встречается раньше в старом списке.
• После выбора позиции pos мы делим грань на две и добавляем новые кандидаты, если внутри граней есть ещё невыбранные элементы.

Если вам нужно решение на другом языке (C++, Java и т.д.), скажите — могу привести аналогичный вариант на требуемом языке.