题目描述

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

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

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

前缀最大值为：666 666 692 692 692，

前缀最大值之和为3408。

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

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

对于第2个数，求出前两个数的最大数，还是666；

对于第3个数，求出前3个数的最大数是692……

其余位置依次类推，最后一次输出第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 666 692 692 692
3408

提示

$-10000<=a_i<=10000$

$1<=n<=100000$