Сможете ли Вы объяснить выбор приза в олимпиадной задачи?

Question

[Виталий К.]

Доброго дня! Столкнулся с простой олимпиадной задачей, вижу решение, но не могу понять почему в примере выходных данных получаются имеено такие значения. Вероятнее всего, Я не правильно понимаю условие, какую-то его часть. Если Вас не затруднит, разъясните доходчиво, почему дела обстоят так.

Призы
Петр участвует в конкурсе, в котором разыгрывается 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 баллов.

Input:
5
1 3 4 2 5

Output:
1 3 3 4

Суть вопроса сводится к моему не понимаю, почему выбирается приз с ценностью 3 при 4-х баллах уже имеющихся. Ведь при 4-х баллах можно было бы взять приз с ценностью 4. Буду премного благодарен за любые попытки ответить. Можете привести код на любом из языков программирования (кроме Brainfuck и иже с ними=), если вам будет удобней так объяснить.

UPD. Чтобы немного больше конкретезировать - я знаю как решить например для этого входного теста, но мое решение будет строиться на основе того, что после 4-ки идет 2-ка, т.к. она меньше, то выведем предыдущее максимальное, т. е. 3. Но мне кажется, что это не решение, а какой-то костыль.

Answer 1

[AltQ]

Ваше решение верно, насколько я понял. Вот весь алгоритм:

Предыдущая максимальная ценность = максимальная ценность = a1

Цикл от 2 до n:
    Ai ≥ максимальной ценности?
        Да:
            вывести максимальную ценность
            предыдущая максимальная ценность = максимальная ценность
            максимальная ценность = Ai

        Нет:
            Ai > прошлой максимальной ценности?
                Да:
                    вывести Ai
                    предыдущая максимальная ценность = Ai

                Нет:
                    вывести прошлую максимальную ценность

Comments

[Виталий К.]

Спасибо за ответ! Да, я такое же решение подразумевал. Единственное что я придумал его эмпирически, на основе выходных данных, а не пользуясь условием. Согласно условию, насколько я понял, должно бы было вывести 1 3 4 4. Если вы сможете еще пояснить, как вы пришли к такой идеи, буду отдельно благодарен!)

Answer 2

[Guru_nachinaushiy]

n = int(input())
a = list(map(int, input().split()))
max1 = max(a[0], a[1])
max2 = min(a[1], a[0])

for i in range(1, n):
if a[i] >= max2:
print(max2, end=" ")
max1 = max2
max2 = a[i]
else:
if a[i] > max1:
print(max1, end=" ")
max1 = a[i]
else:
print(max1, end=" ")