Petya's Prize Guarantee

Petya is participating in a contest where n prizes, numbered from $1$ to $n$, are available. Each prize $i$ has a value of $a_i$. According to the contest rules, a contestant can earn a score between $2$ and $n$. If a contestant obtains a score $k$, he is eligible to win one prize from the set of prizes numbered from $1$ to $k$. However, before he makes his choice, the contest host will remove exactly one prize from the list. Then, Petya can choose one prize from the remaining $k-1$ prizes.

Assuming that the host acts adversarially to minimize Petya's benefit, for each $k$ with $2\le k\le n$, Petya's guaranteed prize value is determined as follows:

• Let $M$ be the maximum value among the prizes $1, 2, \ldots, k$, and let the frequency of $M$ be $f$.
• If $f > 1$, even if the host removes one instance of the maximum, Petya can still choose a prize with value $M$.
• If $f = 1$, the host will remove the only prize with value $M$, and Petya will obtain the second highest value among prizes $1, 2, \ldots, k$.

Given the values of all prizes, determine for every $k$ between $2$ and $n$ the maximum prize value that Petya can guarantee to win.

inputFormat

The first line contains an integer $n$ ($2\le n$), the number of prizes.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$, where $a_i$ represents the value of the $i$-th prize.

outputFormat

Output $n-1$ space-separated integers. The $i$-th integer (corresponding to $k=i+1$) should be the guaranteed prize value Petya can get if he scores $k$.

sample

5
1 2 3 2 5

1 2 2 3