题目描述

求一个数列的所有前缀最小值之和。

即：给出长度为$n$的数列$a_i$,求出对于所有$1<=i<=n$，$min(a_1,a_2,...,a_i)$的和。

比如，有数列：666 304 692 188 596，

前缀最小值为：666 304 304 188 188，

前缀最小值之和为1650。

对于每个位置的前缀最小值解释如下：

对于第1个数666，只有一个数，一定最小；

对于第2个数，求出前两个数的最小数，是304；

对于第3个数，求出前3个数的最小数还是304……

其余位置依次类推，最后一次输出第i个位置的前缀最小值与前缀最小值之和。

输入格式

输入共2行

第01行：一行个正整数n

第02行：n个整数 $a_1、a_2、a_3、a_4…………a_n$

输出格式

输入共2行

第01行：分别表示前i个数的最小值，用空格隔开

第02行：一个整数表示前缀最小值之和

样例 #1

样例输入 #1

5
666 304 692 188 596

样例输出 #1

666 304 304 188 188
1650

提示

$-10000<=a_i<=10000$

$1<=n<=100000$