Choosing Carrot

题意翻译

**题目描述** 下个月就是奶牛Z的生日啦，为了给奶牛Z购买生日礼物，奶牛A和奶牛B决定去挑选奶牛Z最喜欢的青草来作为送给奶牛Z的生日礼物。 现在，奶牛A和奶牛B买来了n堆青草，从左数起，第i堆青草的甜度为ai。奶牛A认为奶牛Z喜欢甜的青草，而奶牛B认为奶牛Z喜欢不甜的青草。因此，奶牛A希望选出来的青草是最甜的，奶牛B希望选出来的是最不甜的青草。 为了解决这个问题，奶牛A与奶牛B决定玩一个游戏，他们俩每次可以从两端的青草开始，选择其中一堆并把这一堆青草吃掉，最后剩下的那一堆青草就是送给奶牛Z的生日礼物，奶牛A先开始吃。 在玩游戏之前，奶牛B去上了一次厕所，奶牛A乘机进行了K次操作，每次操作也是按照要求从这些草堆当中，选择两端的草堆并吃掉其中一堆。在奶牛B回来之后，同样也是奶牛A先开始吃。 奶牛A想知道，对于每一个K（0≤K≤n-1），最后送给奶牛Z的青草甜度分别是多少？ **输入格式** 第一行输入一个数字n（1≤n≤3*10^5），表示青草的总堆数。 第二行输入n个数字ai（1≤ai≤10^9），表示第i堆草的甜度值。 **输出格式** 输出n个数字x0，x1，…，xn-1，表示对于每一个K，最终送给奶牛Z的青草的甜度分别是多少。

题目描述

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?

输入输出格式

输入格式

The first line of input contains a single integer $ n $ ( $ 1<=n<=3·10^{5} $ ) — the total number of carrots. The next line contains $ n $ space-separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ). Here $ a_{i} $ denotes the juiciness of the $ i $ -th carrot from the left of the line.

输出格式

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 $ .

输入输出样例

输入样例 #1

4
1 2 3 5

输出样例 #1

3 3 5 5

输入样例 #2

5
1000000000 1000000000 1000000000 1000000000 1

输出样例 #2

1000000000 1000000000 1000000000 1000000000 1000000000

说明

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 $ .