CF794E 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的青草甜度分别是多少？

无

无

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