← 返回题目列表

Codeforces · 794/E

E. 选择胡萝卜

中文机器翻译题面 查看原题

银行客户奥列格和分析师伊戈尔再次争论。这次,他们想挑选一份礼物送给他们的朋友,程序员 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亿多汁。