CF794E.Choosing Carrot

Oleg the bank client and Igor the analyst are arguing again. This time, they want to pick a gift as a present for their friend, ZS the coder. After a long thought, they decided that their friend loves to eat carrots the most and thus they want to pick the best carrot as their present.

There are n carrots arranged in a line. The i-th carrot from the left has juiciness a__i. Oleg thinks ZS loves juicy carrots whereas Igor thinks that he hates juicy carrots. Thus, Oleg would like to maximize the juiciness of the carrot they choose while Igor would like to minimize the juiciness of the carrot they choose.

To settle this issue, they decided to play a game again. Oleg and Igor take turns to play the game. In each turn, a player can choose a carrot from either end of the line, and eat it. The game ends when only one carrot remains. Oleg moves first. The last remaining carrot will be the carrot that they will give their friend, ZS.

Oleg is a sneaky bank client. When Igor goes to a restroom, he performs k moves before the start of the game. Each move is the same as above (eat a carrot from either end of the line). After Igor returns, they start the game with Oleg still going first.

Oleg wonders: for each k such that 0 ≤ k ≤ n - 1, what is the juiciness of the carrot they will give to ZS if he makes k extra moves beforehand and both players play optimally?

银行客户奥列格与分析师伊戈尔再次发生了争执。这一次，他们想为朋友——程序员 ZS 挑选一份礼物。经过长时间思考，他们认定朋友最爱吃胡萝卜，因此决定挑选一根“最佳”胡萝卜作为礼物。

共有 $n$ 根胡萝卜排成一行。从左往右数第 $i$ 根胡萝卜的多汁程度为 $a_i$。奥列格认为 ZS 喜欢多汁的胡萝卜，而伊戈尔则认为 ZS 讨厌多汁的胡萝卜。因此，奥列格希望最终选出的胡萝卜尽可能多汁，而伊戈尔则希望其尽可能不多汁（即多汁程度最小）。

为解决分歧，他们决定再次进行一场游戏。奥列格与伊戈尔轮流进行操作。每轮中，当前玩家可从该行胡萝卜的左端或右端选取一根并吃掉它。当仅剩一根胡萝卜时，游戏结束。这最后一根胡萝卜即为他们将赠予朋友 ZS 的礼物。奥列格先手。

奥列格是个狡猾的银行客户。在伊戈尔去洗手间期间，他预先进行了 $k$ 次操作（即“额外移动”），每次操作与游戏中相同：从当前行的左端或右端吃掉一根胡萝卜。待伊戈尔返回后，两人再按原规则开始游戏，且奥列格仍为先手。

奥列格想知道：对每个满足 $0 \leq k \leq n-1$ 的 $k$，若他在游戏开始前预先执行 $k$ 次额外移动，且此后双方均以最优策略进行游戏，则最终赠予 ZS 的胡萝卜的多汁程度是多少？

The first line of input contains a single integer n (1 ≤ n ≤ 3·105) — the total number of carrots.

The next line contains n space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109). Here a__i denotes the juiciness of the i-th carrot from the left of the line.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）——胡萝卜的总数。

下一行包含 $n$ 个用空格分隔的整数 $a_1,\,a_2,\,\ldots,\,a_n$（$1 \leq a_i \leq 10^9$）。其中 $a_i$ 表示从左到右第 $i$ 根胡萝卜的多汁程度。

Output n space-separated integers _x_0, _x_1, ..., x__n - 1. Here, x__i denotes the juiciness of the carrot the friends will present to ZS if k = i.

输出 n 个以空格分隔的整数 _x_₀, _x_₁, ..., x__n − 1。其中，x__i 表示当 k = i 时，朋友们将献给 ZS 的胡萝卜的多汁程度。

For the first example,

When k = 0, one possible optimal game is as follows:

• Oleg eats the carrot with juiciness 1.
• Igor eats the carrot with juiciness 5.
• Oleg eats the carrot with juiciness 2.
• The remaining carrot has juiciness 3.

When k = 1, one possible optimal play is as follows:

• Oleg eats the carrot with juiciness 1 beforehand.
• Oleg eats the carrot with juiciness 2.
• Igor eats the carrot with juiciness 5.
• The remaining carrot has juiciness 3.

When k = 2, one possible optimal play is as follows:

• Oleg eats the carrot with juiciness 1 beforehand.
• Oleg eats the carrot with juiciness 2 beforehand.
• Oleg eats the carrot with juiciness 3.
• The remaining carrot has juiciness 5.

When k = 3, one possible optimal play is as follows:

• Oleg eats the carrot with juiciness 1 beforehand.
• Oleg eats the carrot with juiciness 2 beforehand.
• Oleg eats the carrot with juiciness 3 beforehand.
• The remaining carrot has juiciness 5.

Thus, the answer is 3, 3, 5, 5.

For the second sample, Oleg can always eat the carrot with juiciness 1 since he always moves first. So, the remaining carrot will always have juiciness 1000000000.

对于第一个样例：

当 $k = 0$ 时，一种可能的最优游戏过程如下：

• Oleg 吃掉汁水值为 1 的胡萝卜。
• Igor 吃掉汁水值为 5 的胡萝卜。
• Oleg 吃掉汁水值为 2 的胡萝卜。
• 剩余胡萝卜的汁水值为 3。

当 $k = 1$ 时，一种可能的最优玩法如下：

• Oleg 提前吃掉汁水值为 1 的胡萝卜。
• Oleg 吃掉汁水值为 2 的胡萝卜。
• Igor 吃掉汁水值为 5 的胡萝卜。
• 剩余胡萝卜的汁水值为 3。

当 $k = 2$ 时，一种可能的最优玩法如下：

• Oleg 提前吃掉汁水值为 1 的胡萝卜。
• Oleg 提前吃掉汁水值为 2 的胡萝卜。
• Oleg 吃掉汁水值为 3 的胡萝卜。
• 剩余胡萝卜的汁水值为 5。

当 $k = 3$ 时，一种可能的最优玩法如下：

• Oleg 提前吃掉汁水值为 1 的胡萝卜。
• Oleg 提前吃掉汁水值为 2 的胡萝卜。
• Oleg 提前吃掉汁水值为 3 的胡萝卜。
• 剩余胡萝卜的汁水值为 5。

因此，答案为 $3,\,3,\,5,\,5$。

对于第二个样例，Oleg 总是先手，因此他总能吃掉汁水值为 1 的胡萝卜。所以，剩余胡萝卜的汁水值恒为 $1000000000$。