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 p1,p2,...,pn 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.
The first line contains one integer n (1≤n≤105) - the number of numbers in the sequence. The second line contains n integers pi (1≤pi≤n) - elements of the sequence.
Print the required amount corresponding to the given sequence.