English · Original
Chinese · Translation
Formal · Original
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?
## Input
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.
## Output
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_.
[samples]
## Note
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.
Oleg（银行客户）和 Igor（分析师）又在争论了。这次，他们想为朋友 ZS（程序员）挑选一份礼物。经过长时间思考，他们决定 ZS 最爱吃胡萝卜，因此他们想挑选最棒的胡萝卜作为礼物。
有 #cf_span[n] 根胡萝卜排成一列。从左数第 #cf_span[i] 根胡萝卜的多汁度为 #cf_span[ai]。Oleg 认为 ZS 喜欢多汁的胡萝卜，而 Igor 认为 ZS 讨厌多汁的胡萝卜。因此，Oleg 希望最大化他们选择的胡萝卜的多汁度，而 Igor 希望最小化它。
为了解决这个问题，他们决定再次玩游戏。Oleg 和 Igor 轮流进行游戏。每轮中，一名玩家可以从队伍的任一端选择一根胡萝卜并吃掉它。当只剩一根胡萝卜时，游戏结束。Oleg 先手。最后一根剩余的胡萝卜将作为他们送给 ZS 的礼物。
Oleg 是个狡猾的银行客户。当 Igor 去洗手间时，他在游戏开始前进行 #cf_span[k] 次移动。每次移动与上述规则相同（从队伍任一端吃掉一根胡萝卜）。Igor 回来后，他们开始游戏，Oleg 仍然先手。
Oleg 想知道：对于每个 #cf_span[k]（满足 #cf_span[0 ≤ k ≤ n - 1]），如果他事先进行 #cf_span[k] 次额外移动，且双方都采取最优策略，他们最终送给 ZS 的胡萝卜的多汁度是多少？
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 3·105]）——胡萝卜的总数。
第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）。这里 #cf_span[ai] 表示从左数第 #cf_span[i] 根胡萝卜的多汁度。
输出 #cf_span[n] 个空格分隔的整数 #cf_span[x0, x1, ..., xn - 1]。其中 #cf_span[xi] 表示当 #cf_span[k = i] 时，朋友们送给 ZS 的胡萝卜的多汁度。
## Input
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 3·105]）——胡萝卜的总数。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）。这里 #cf_span[ai] 表示从左数第 #cf_span[i] 根胡萝卜的多汁度。
## Output
输出 #cf_span[n] 个空格分隔的整数 #cf_span[x0, x1, ..., xn - 1]。其中 #cf_span[xi] 表示当 #cf_span[k = i] 时，朋友们送给 ZS 的胡萝卜的多汁度。
[samples]
## Note
对于第一个例子：
当 #cf_span[k = 0] 时，一种可能的最优游戏过程如下：
Oleg 吃掉多汁度为 #cf_span[1] 的胡萝卜。Igor 吃掉多汁度为 #cf_span[5] 的胡萝卜。Oleg 吃掉多汁度为 #cf_span[2] 的胡萝卜。剩余胡萝卜的多汁度为 #cf_span[3]。
当 #cf_span[k = 1] 时，一种可能的最优玩法如下：
Oleg 在游戏前吃掉多汁度为 #cf_span[1] 的胡萝卜。Oleg 吃掉多汁度为 #cf_span[2] 的胡萝卜。Igor 吃掉多汁度为 #cf_span[5] 的胡萝卜。剩余胡萝卜的多汁度为 #cf_span[3]。
当 #cf_span[k = 2] 时，一种可能的最优玩法如下：
Oleg 在游戏前吃掉多汁度为 #cf_span[1] 的胡萝卜。Oleg 在游戏前吃掉多汁度为 #cf_span[2] 的胡萝卜。Oleg 吃掉多汁度为 #cf_span[3] 的胡萝卜。剩余胡萝卜的多汁度为 #cf_span[5]。
当 #cf_span[k = 3] 时，一种可能的最优玩法如下：
Oleg 在游戏前吃掉多汁度为 #cf_span[1] 的胡萝卜。Oleg 在游戏前吃掉多汁度为 #cf_span[2] 的胡萝卜。Oleg 在游戏前吃掉多汁度为 #cf_span[3] 的胡萝卜。剩余胡萝卜的多汁度为 #cf_span[5]。
因此，答案是 #cf_span[3, 3, 5, 5]。
对于第二个例子，由于 Oleg 总是先手，他总能吃掉多汁度为 #cf_span[1] 的胡萝卜。因此，剩余的胡萝卜总是具有多汁度 #cf_span[1000000000]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of carrots.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers representing juiciness, where $ a_i \in \mathbb{Z}^+ $.
For each $ k \in \{0, 1, \dots, n-1\} $, let $ A_k $ denote the sequence after Oleg performs $ k $ preliminary moves (each removing one carrot from either end), followed by a two-player alternating game starting with Oleg, where players alternately remove a carrot from either end until one remains. Both play optimally: Oleg maximizes the final juiciness, Igor minimizes it.
**Constraints**
1. $ 1 \le n \le 3 \cdot 10^5 $
2. $ 1 \le a_i \le 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each $ k \in \{0, 1, \dots, n-1\} $, compute $ x_k $, the juiciness of the last remaining carrot when:
- Oleg removes $ k $ carrots from either end (optimally, to maximize final result),
- Then the game proceeds with alternating moves (Oleg first), removing from either end,
- Both players play optimally during the game phase.
Output $ (x_0, x_1, \dots, x_{n-1}) $.
API Response (JSON)
{
"problem": {
"name": "E. Choosing Carrot",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF794E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Oleg（银行客户）和 Igor（分析师）又在争论了。这次，他们想为朋友 ZS（程序员）挑选一份礼物。经过长时间思考，他们决定 ZS 最爱吃胡萝卜，因此他们想挑选最棒的胡萝卜作为礼物。\n\n有 #cf_span[n] 根胡萝卜排成一列。从左数第 #cf_span[i] 根胡萝卜的多汁度为 #cf_span[ai]。Oleg 认为 ZS 喜欢多汁的胡萝卜，而 Igor 认为 ZS 讨厌多汁的胡萝卜。因...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of carrots. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers representing juiciness, where $ a_i \\in \\mathbb{Z}^+ $. \n\nFor eac...",
"is_translate": false,
"language": "Formal"
}
]
}