P17442 Delete the First or Last / Delete and Backspace

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.

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 $n$ integers. The $k$-th integer should be the maximum score achievable when performing exactly $k$ operations.

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