给定一个长度为 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。

前60%的数据：1\le n\le 1000,1 \leq a_i \leq 10^9。

前100%的数据：1\le n\le 10^5,1 \leq a_i \leq 10^9。