银行客户奥列格和分析师伊戈尔再次争论。这次,他们想挑选一份礼物送给他们的朋友,程序员 ZS。想了很久,他们决定朋友最喜欢吃胡萝卜,所以他们想挑选最好的胡萝卜作为礼物。
有n根胡萝卜排成一排。左边第 i 个胡萝卜多汁 ai。 Oleg 认为 ZS 喜欢多汁的胡萝卜,而 Igor 认为他讨厌多汁的胡萝卜。因此,奥列格希望最大化他们选择的胡萝卜的多汁性,而伊戈尔希望最小化他们选择的胡萝卜的多汁性。
为了解决这个问题,他们决定再玩一次游戏。奥列格和伊戈尔轮流玩这个游戏。在每个回合中,玩家可以从线的两端选择一根胡萝卜并吃掉它。当只剩下一根胡萝卜时,游戏结束。奥列格先动。最后剩下的胡萝卜将是他们送给朋友 ZS 的胡萝卜。
Oleg 是一位狡猾的银行客户。当 Igor 去洗手间时,他会在游戏开始前执行 k 个动作。每个动作与上面相同(从线的两端吃一根胡萝卜)。伊戈尔回来后,他们开始比赛,奥列格仍然是第一。
Oleg 想知道:对于每个 k,使得 0 ≤ k ≤ n - 1,如果 ZS 提前进行 k 次额外动作并且双方都发挥最佳状态,那么他们会给 ZS 的胡萝卜的多汁性是多少?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 3·105) — 胡萝卜的总数。
下一行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。这里 ai 表示从该行左边算起第 i 个胡萝卜的多汁度。
输出
输出 n 个空格分隔的整数 x0, x1, ..., xn - 1。这里,xi 表示如果 k = i,朋友们将赠送给 ZS 的胡萝卜的多汁程度。
示例
输入 #1
4 1 2 3 5
输出 #1
3 3 5 5
输入 #2
5 1000000000 1000000000 1000000000 1000000000 1
输出 #2
1000000000 1000000000 1000000000 1000000000 1000000000
注意
对于第一个示例,
当k=0时,一种可能的最优博弈如下:
- 奥列格吃着多汁的胡萝卜1。
- 伊戈尔吃着多汁的胡萝卜 5。
- 奥列格吃着多汁的胡萝卜2。
- 剩下的胡萝卜多汁3。
当 k = 1 时,一种可能的最佳玩法如下:
- 奥列格事先吃了多汁的胡萝卜1。
- 奥列格吃着多汁的胡萝卜2。
- 伊戈尔吃着多汁的胡萝卜 5。
- 剩下的胡萝卜多汁3。
当 k = 2 时,一种可能的最佳玩法如下:
- 奥列格事先吃了多汁的胡萝卜1。
- 奥列格事先吃了多汁的胡萝卜2。
- 奥列格吃着多汁的胡萝卜3。
- 剩余的胡萝卜多汁度为 5。
当 k = 3 时,一种可能的最佳玩法如下:
- 奥列格事先吃了多汁的胡萝卜1。
- 奥列格事先吃了多汁的胡萝卜2。
- 奥列格事先吃掉了多汁的胡萝卜 3。
- 剩余的胡萝卜多汁度为 5。
因此,答案是 3, 3, 5, 5。
对于第二个样本,Oleg 总是可以吃到多汁度为 1 的胡萝卜,因为他总是先移动。所以,剩下的胡萝卜总会有10亿多汁。