题目描述

给定一个长度为 $n$ 的数组 $a$。对于每个 $k=1,2,\ldots,n$，独立地考虑以下过程：

初始时数组为 $a$。你需要进行恰好 $k$ 次操作，每次操作可以选择以下两种方式之一：

• Backspace：删除当前数组的第一个元素；
• Delete：删除当前数组的最后一个元素。

你的得分定义为第 $k$ 次操作中被删除元素的值。

对于每个 $k=1,2,\ldots,n$，求你能够获得的最大得分。

输入格式

第一行包含一个整数 $n$，表示数组的长度 $(1\le n\le 10^5)$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组 $a$ $(1\le a_i\le 10^9)$。

输出格式

输出 $n$ 个整数，其中，第 $k$ 个整数表示恰好进行 $k$ 次操作时能够获得的最大得分。

样例

5
2 7 8 1 4

4 7 8 8 8

样例说明

对于 $k=1$，只能删除数组最左边的 $2$ 或最右边的 $4$，因此最大得分为 $4$。

对于 $k=2$，可以第一次删除最左边的 $2$，第二次再删除最左边的 $7$，此时第二次操作删除的元素为 $7$，因此最大得分为 $7$。

对于 $k=3$，可以依次删除最左边的 $2,7,8$，使第三次操作删除的元素为 $8$，因此最大得分为 $8$。

对于 $k=4$ 和 $k=5$，同样可以合理安排前面的操作，使最后一次操作删除的元素为 $8$。