Background

源码星球上有一种有趣的游戏「小，小小小」。

Description

给你 $n$ 张卡片，第 $i$ 张卡片上写着 $a_i$。

定义一个包含 $n$ 张卡片的卡片组分值为：

其中 $a_{n+1} = a_1$。

卡片的顺序显然会影响其分值，所以你需要将其以某种方式排列以得到最小的分值。

因为游戏要求，你还需要对卡片的每个前缀计算将其排列后能得到的最小分值。

Format

Input

第一行一个正整数 $n$，表示卡片数。

第二行 $n$ 个整数，第 $i$ 个表示 $a_i$。

Output

$n$ 行每行一个整数，即你能从卡片 $[1, i]$ 中得到的最小分值。

Samples

5
5 3 4 4 7

0
4
4
4
8

Limitation

对于 $100 \%$ 的数据，$1 \le n \le 10^6, 0 \le a_i \lt 2^{31}$。