Prizes
Time limit1sMemory limit512 MB
For each k from 2 to n, find the maximum prize value that is guaranteed among prizes 1..k when the host may remove one prize before Petya picks.
- Level
Medium6 of 10
- Topics
- Array, Prefix sum, Greedy, Sorting
- Solved
- No attempts yet
Problem
Petya takes part in a contest with n prizes. The prizes are numbered from 1 to n.
Based on the results of the contest, a participant can score from 2 to n points. If a participant scores k points, they receive one of the prizes numbered from 1 to k. Before the participant chooses a prize, the host removes one prize from the list. Then the participant can choose any prize from the remaining k - 1.
Petya learned the list of prizes. He determined the value of each prize; the value of the i-th prize is the integer ai.
Given the values of the prizes, write a program that for each k from 2 to n determines the prize with the maximum value that Petya is guaranteed to receive if he scores k points in the contest.
Input
The first line contains the number n. (2 ≤ n ≤ 100 000) The second line contains n integers: a1, a2, …, an. (1 ≤ ai ≤ 10^9)
Output
The output must contain a single line with n - 1 integers: for each k from 2 to n, the value of the prize Petya will receive if he scores k points.