Can you explain the choice of the prize in the Olympiad problem?

Question

Programming

Good day! I came across a simple Olympiad problem, I see the solution, but I can’t understand why such values ​​are obtained in the example output. Most likely, I do not understand the condition correctly, some part of it. If you don't mind, explain intelligibly why things are the way they are.
Prizes
Petr takes part in a competition where n prizes are drawn. Prizes are numbered from 1 to n.
According to the results of the competition, the participant can score from 2 to n points. If the participant scores k points, he will receive one of the prizes with a number from 1 to k. Before the participant chooses his prize, the host of the competition removes one of the prizes from the list. Then the participant can choose any prize from the remaining k - 1.
The list of prizes became known to Peter. He determined for each prize its value, for the i-th prize it is given by the integer Ai.
It is required to write a program that, given the values ​​of the prizes, determines for each k from 2 to n the prize with the maximum value that Peter is guaranteed to get if he scores k points in the competition.
Input data format:
The first line of the input file contains the number n (2 ≤ n ≤ 100 000). The second line of this file contains n integers: a1, a2, …, an (1 ≤ ai ≤ 109).
Output data format:
The output file should contain one line containing n - 1 integers: for each k from 2 to n, the value of the prize that Peter will get if he scores k points should be displayed.

Input:
5
1 3 4 2 5

Output:
1 3 3 4

The essence of the question boils down to my not understanding why a prize with a value of 3 is chosen with 4 points already available. Indeed, with 4 points , one could take a prize with a value of 4. I would be very grateful for any attempts to answer. You can provide code in any of the programming languages ​​(except Brainfuck and others like them =), if it would be more convenient for you to explain it this way.
UPD. To be a little more specific - I know how to solve for example for this input test, but my solution will be based on the fact that after 4 comes 2, because it is less, then we will display the previous maximum, i.e. 3. But it seems to me that this is not a solution, but some kind of crutch.

Answer 1

Your solution is correct as far as I understand. Here is the whole algorithm:

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

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

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

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