eolymp
bolt
Try our new interface for solving problems
Problems

Simple sum

Simple sum

Time limit 1 second
Memory limit 128 MiB

Nikhat arranged the numbers 1, 2, ... , n in ascending order. Later Hussein came and swapped some of these numbers. Now we have some mixed sequence p_1, p_2, ..., p_n of numbers from 1 to n.

Calculate the following sum for this sequence:

\sum_{l = 1}^N \sum_{r = l}^N min(p_l, p_{l+1}, ..., p_r)

Simply put, you need to find the sum of all the minimum numbers in all subsequences of a given sequence.

The min function finds the minimum of the given numbers.

Input data

The first line contains one integer n(1 ≤ n ≤ 10^5) - the number of numbers in the sequence. The second line contains n integers p_i(1 ≤ p_i ≤ n) - elements of the sequence.

Output data

Print the required amount corresponding to the given sequence.

Examples

Input example #1
3
2 1 3

Output example #1
9

Input example #2
4
1 2 3 4

Output example #2
20

Author Rafael Saddatimov
Source Azərbaycan Milli İnformatika Olimpiadası – Final Turu 5 May 2019