1739 - 极值的和
Description
给定一个序列 �1,�2,�3,…,��a1,a2,a3......an，请求出该序列每一个连续子序列的最大值，并计算这些最大值的和。
也就是求出 
Input
第一行：单个整数 �n
第二行：�n 个整数表示 �1,�2,…,��a1,a2,a3......an，
Output
单个整数：表示所有区间最大数的和
Examples
Input
2 6 8
Output
22
Input
3 4 5 6
Output
32
Hint
对于 30%30% 的数据，1≤�≤5001≤n≤500
对于 60%60% 的数据，1≤�≤50,0001≤n≤50,000
对于 100%100% 的数据，1≤�≤500,0001≤n≤500,000
0≤��≤1,000,0000≤ai≤1,000,000