Median Triangulation

問題文

正整数 $N$ と長さ $N$ の正整数列 $A$ が与えられる。

正 $N$ 角形があり、頂点には反時計回りに $1,2,\dots,N$ の番号が振られている。頂点 $i$ には $A_i$ が書かれている。

この多角形に、内部で交差しないように $N-3$ 本の対角線を引き、$N-2$ 個の三角形に分割する。

各三角形について、その $3$ 頂点に書かれた整数の中央値を昇順に並べた数列を $B$ とする。

このようにして得られる $B$ のうち、辞書順で最大のものを求めよ。

制約

• 入力はすべて整数である。
• $3 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$

入力

入力は以下の形式で標準入力から与えられる。

出力

辞書順で最大となる数列 $B$ の各要素を空白区切りで出力せよ。

サンプル

サンプル 1

入力

6
2 7 1 8 4 6

出力

6 6 7 7

頂点 $2$ と $4$、頂点 $4$ と $6$、頂点 $2$ と $6$ をそれぞれ結ぶ対角線を引くと、次の $4$ 個の三角形に分割される。

• 頂点 $(1,2,6)$ からなる三角形：中央値は $6$
• 頂点 $(2,3,4)$ からなる三角形：中央値は $7$
• 頂点 $(4,5,6)$ からなる三角形：中央値は $6$
• 頂点 $(2,4,6)$ からなる三角形：中央値は $7$

このとき $B=(6,6,7,7)$ となり、これが辞書順で最大である。