# Simple sum

Easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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:

$l=1∑N 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

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

Print the required amount corresponding to the given sequence.

## Examples

Input #1

Answer #1

Input #2

Answer #2

Submissions 731

Acceptance rate 21%