Условие:
Петр участвует в конкурсе, в котором разыгрывается n призов. Призы пронумерованы от 1 до n.
По итогам конкурса участник может набрать от 2 до n баллов. Если участник наберет k баллов, то он получит один из призов с номером от 1 до k. Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся k – 1.
Список призов стал известен Петру. Он определил для каждого приза его ценность, для i-го приза она задается целым числом ai.
Требуется написать программу, которая по заданным ценностям призов определяет для каждого k от 2 до n, приз с какой максимальной ценностью гарантированно достанется Петру, если он наберет в конкурсе k баллов.
Формат входных данных:
Первая строка входного файла содержит число n (2 ≤ n ≤ 100 000). Вторая строка этого файла содержит n целых чисел: a1, a2, …, an (1 ≤ ai ≤ 109).
Формат выходных данных:
Выходной файл должен содержать одну строку, содержащую n – 1 целых чисел: для каждого k от 2 до n должна быть выведена ценность приза, который достанется Петру, если он наберет k баллов.

Задача требует нахождения призов с максимальной ценностью, которые Петру могут гарантированно достаться в зависимости от количества баллов, которые он наберет.

Условие задачи:

1. В конкурсе разыгрывается n призов, каждый из которых имеет свою ценность.
2. Петя может набрать от 2 до n баллов. Если он набрал k баллов, то он может выбрать один из оставшихся k-1 призов (после того как один приз будет удален ведущим).
3. Задача — для каждого возможного значения баллов (от 2 до n) найти максимальную ценность приза, который Петя гарантированно получит.

Разбор задачи:

Предположим, что Петя набрал k баллов. В этом случае:

• Перед тем как Петя выберет приз, ведущий удаляет один из призов. Из оставшихся k призов, Петя может выбрать любой, но он выберет тот, который для него наиболее выгоден (с максимальной ценностью).
• Это значит, что нужно просто выбрать максимальную ценность среди оставшихся k-1 призов.

Для каждого k от 2 до n нам нужно найти максимальную ценность среди первых k призов, после того как один из них был удален. Это означает, что если удалить минимальный приз среди первых k призов, то максимальная ценность останется среди оставшихся.

Алгоритм:

1. Для каждого значения k от 2 до n определим, какой приз с максимальной ценностью может быть выбран.
2. Чтобы быстро находить максимальную ценность среди первых k-1 призов после удаления минимального, можно использовать структуру данных, которая будет поддерживать максимум среди k-1 элементов.

Подход с использованием префиксных максимумов:

1. Создадим массив prefix_max, где prefix_max[k] — это максимальное значение среди первых k элементов.
2. Для каждого k от 2 до n, ответом будет максимальное значение среди первых k-1 элементов.

Пошаговое решение:

1. Прочитаем входные данные: количество призов n и список их ценностей.
2. Построим массив префиксных максимумов, где каждый элемент будет хранить максимальную ценность среди всех элементов от 1 до текущего индекса.
3. Для каждого k от 2 до n выведем результат, который будет равен максимальному значению среди первых k-1 элементов.

Пример:

Вход:

5
10 20 15 30 25

Выход:

20 20 30 30

Решение на Python:

python
n = int(input())  # Читаем количество призов
a = list(map(int, input().split()))  # Читаем массив ценностей призов
# Массив для хранения максимальных ценностей среди первых k элементов
prefix_max = [0] * n
# Заполняем массив префиксных максимумов
prefix_max[0] = a[0]
for i in range(1, n):
    prefix_max[i] = max(prefix_max[i-1], a[i])
# Ответ для каждого k от 2 до n будет храниться в списке
result = []
for k in range(2, n+1):
    result.append(prefix_max[k-2])  # Максимум среди первых k-1 элементов
# Выводим результат
print(" ".join(map(str, result)))

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

1. Сначала считываем количество призов n и массив ценностей призов a.
2. Создаем массив prefix_max, в котором храним максимальное значение среди первых k элементов массива ценностей.
3. Затем для каждого значения k от 2 до n добавляем в результат максимальное значение среди первых k-1 элементов, используя уже построенный массив префиксных максимумов.
4. Выводим результат.

Время выполнения:

• Сложность этого алгоритма — O(n), потому что мы дважды проходим по массиву: первый раз для заполнения массива префиксных максимумов, второй раз для вывода результата.
• Это оптимальное решение для задачи, так как оно эффективно использует префиксные массивы для быстрого поиска максимальных значений.

Заключение:

Таким образом, решение задачи сводится к построению массива префиксных максимумов и затем быстрому извлечению ответов для каждого значения k от 2 до n.