P17442 掐头去尾 / Delete and Backspace

给定一个长度为 $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$ 次操作时能够获得的最大得分。

对于 $k=1$，只能删除数组最左边的 $2$ 或最右边的 $4$，因此最大得分为 $4$。 对于 $k=2$，可以第一次删除最左边的 $2$，第二次再删除最左边的 $7$，此时第二次操作删除的元素为 $7$，因此最大得分为 $7$。 对于 $k=3$，可以依次删除最左边的 $2,7,8$，使第三次操作删除的元素为 $8$，因此最大得分为 $8$。 对于 $k=4$ 和 $k=5$，同样可以合理安排前面的操作，使最后一次操作删除的元素为 $8$。