给定一个序列 �1,�2,�3,…,��a1,a2,a3......an，请求出该序列每一个连续子序列的最大值，并计算这些最大值的和。

也就是求出         

• 第一行：单个整数 $n$

• 第二行：$n$ 个整数表示 �1,�2,…,��a1,a2,a3......an，

• 单个整数：表示所有区间最大数的和

• 对于 $30\%$ 的数据，$1\le n\le 500$

• 对于 $60\%$ 的数据，$1\le n\le 50,000$

• 对于 $100\%$ 的数据，$1\le n\le 500,000$

• $0\le ai\le 1,000,000$