题目描述

下个月就是奶牛Z的生日啦，为了给奶牛Z购买生日礼物，奶牛A和奶牛B决定去挑选奶牛Z最喜欢的青草来作为送给奶牛Z的生日礼物。 现在，奶牛A和奶牛B买来了n堆青草，从左数起，第 $i$ 堆青草的甜度为 $a_i$。奶牛A认为奶牛Z喜欢甜的青草，而奶牛B认为奶牛Z喜欢不甜的青草。因此，奶牛A希望选出来的青草是最甜的，奶牛B希望选出来的是最不甜的青草。为了解决这个问题，奶牛A与奶牛B决定玩一个游戏，他们俩每次可以从两端的青草开始，选择其中一堆并把这一堆青草吃掉，最后剩下的那一堆青草就是送给奶牛Z的生日礼物，奶牛A先开始吃。 在玩游戏之前，奶牛B去上了一次厕所，奶牛A乘机进行了K次操作，每次操作也是按照要求从这些草堆当中，选择两端的草堆并吃掉其中一堆。在奶牛B回来之后，同样也是奶牛A先开始吃。 奶牛A想知道，对于每一个 $K$（$0 \le K < n$），最后送给奶牛Z的青草甜度分别是多少？

输入格式

第一行输入一个数字 $n$（$1 \le n \le 3 \times 10^5$），表示青草的总堆数。

第二行输入 $n$ 个数字，第 $i$ 个数表示第 $i$ 堆草的甜度值为 $a_i$ （$1 \le a_i \le 10^9$）。

输出格式

输出 $n$ 个数字 $x_0$，$x_1$，…，$x_n-1$，表示对于每一个 $K$，最终送给奶牛Z的青草的甜度分别是多少。