Simple sum

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:

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

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

Output

Print the required amount corresponding to the given sequence.

Examples