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