A. Delete and Backspace
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 two actions:

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

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

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

Input

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

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

Output

Output $$$n$$$ integers. The $$$k$$$-th integer should be the maximum score you can obtain after performing exactly $$$k$$$ operations.

Example
Input
5
2 7 8 1 4
Output
4 7 8 8 8
Note

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

For $$$k=2$$$, we can first delete the leftmost element $$$2$$$, and then delete the new leftmost element $$$7$$$. Thus, the element deleted in the second operation is $$$7$$$, so the maximum score is $$$7$$$.

For $$$k=3$$$, we can delete the leftmost elements $$$2,7,8$$$ in order, making the element deleted in the third operation equal to $$$8$$$. Therefore, the maximum score is $$$8$$$.

For $$$k=4$$$ and $$$k=5$$$, we can similarly arrange the previous operations so that the element deleted in the last operation is $$$8$$$.