Problem Description

You are given an array $a$ of length $n$. For each $k=1,2,\ldots,n$, consider the following process independently.

Initially, the array is $a$. You must perform exactly $k$ operations. In each operation, you may choose one of the following:

• Backspace: delete the first element of the current array.
• Delete: delete the last element of the current array.

Your score is defined as the value of the element deleted in the $k$-th operation.

For each $k=1,2,\ldots,n$, find the maximum score you can obtain.

Input Format

The first line contains an integer $n$, the length of the array ($1\le n\le 10^5$).

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$, representing the array $a$ ($1\le a_i\le 10^9$).

Output Format

Output $n$ integers. The $k$-th integer should be the maximum score achievable when performing exactly $k$ operations.

5
2 7 8 1 4

4 7 8 8 8

Hint

For $k=1$, you can only delete the leftmost $2$ or the rightmost $4$, so the maximum score is $4$.

For $k=2$, you can delete the leftmost $2$ first, then delete the leftmost $7$. The element deleted in the second operation is $7$, so the maximum score is $7$.

For $k=3$, you can delete the leftmost $2,7,8$ in order, making the element deleted in the third operation $8$, so the maximum score is $8$.

For $k=4$ and $k=5$, you can also arrange the earlier operations properly, so that the element deleted in the last operation is still $8$.

Translated by ChatGPT 5