CF794E Choosing Carrot

Oleg 和 Igor 想要为 ZS 准备一份礼物。由于 ZS 喜欢吃胡萝卜，所以他们想挑最好的胡萝卜作为礼物。 现在有 $n$ 根胡萝卜排成一行，左起第 $i$ 根有 $a_i$ 的水分。Oleg 认为 ZS 喜欢多汁的（即 $a_i$ 更大的）胡萝卜，而 Igor 则认为 ZS 喜欢干的（即 $a_i$ 更小的）胡萝卜。所以，Oleg 想最大化所选胡萝卜的水分，Igor 则想最小化之。 为了解决这个问题，他们决定再玩一次游戏。Oleg 和 Igor 轮流行动，Oleg 先手。 在每个回合中，玩家可以从序列的任一端选择一根胡萝卜并吃掉。当只剩下一根胡萝卜时，游戏结束，最后剩下的胡萝卜将送给 ZS。 但是在游戏开始前，Igor 去洗手间时，Oleg 先进行了 $k$ 次操作。Igor 回来后，他们依旧以 Oleg 先手开始游戏。 Oleg 想知道，对于每个 $0\le k\le n-1$，最后送给 ZS 的胡萝卜水分是多少？

第一行一个整数 $n(1\le n\le 3\times 10^5)$，表示胡萝卜的数量。 第二行 $n$ 个整数 $a_i(1\le a_i\le 10^9)$，第 $i$ 个数表示第 $i$ 根胡萝卜的水分。

一行 $n$ 个数字 $x_0,x_1,\dots,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 $ .