Chocolates :
Difficulty Level : Medium
Submissions : 165
Asked In :
Marks :30
: 4 | : 1
Bob has $$$N$$$ chocolates in his refrigerator to which he gives special value. He performs some operations on the chocolates. In each operation, he takes one or more chocolates that are lying in a continuous manner. He then finds and notes down the minimum special value of a chocolate in that group of chocolates. He performs this operation for all groups of chocolates he could find.
The task is to find the sum of all the numbers he had written.
Input
The first line contains an integer $$$N$$$. The second line contains an array $$$A_{i}$$$ representing the special value of chocolates.$$$(1 \le N,A_{i} \le 10^5).$$$
Output
The desired sum.
Examples
Input
2 3 4
Output
10
Input
5 1 1 1 1 1
Output
15
