One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

<image>

Constraints

* 1 ≦ N ≦ 200,000
* (a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:


N
a_1 a_2 ... a_N


Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Examples

Input

3
2 1 3


Output

9


Input

4
1 3 2 4


Output

19


Input

8
5 4 8 1 2 6 7 3


Output

85
/* AtCoder My Practice
 * author: Leonardone @ NEETSDKASU
 */
import java.util.Scanner;
 
public class Main
{
    static class Range
    {
        int lower, upper;
        Range lbound = null, ubound = null;
        Range(int l, int u) { lower = l; upper = u; }
    }
    
    static Range range;
    static long sum = 0L;
    
    static void calc(int value, int index)
    {
        Range tmp = range;
        long len;
        for (;;)
        {
            if (tmp.lower <= index && index <= tmp.upper)
            {
                len = (long)(tmp.upper - tmp.lower + 1);
                sum += (len * (len + 1L) / 2L) * (long)value;
                len = (long)(tmp.upper - index);
                sum -= (len * (len + 1L) / 2L) * (long)value;
                len = (long)(index - tmp.lower);
                sum -= (len * (len + 1L) / 2L) * (long)value;
                if (tmp.lower == index)
                {
                    tmp.lower++;
                }
                else if (tmp.upper == index)
                {
                    tmp.upper--;
                }
                else
                {
                    tmp.lbound = new Range(tmp.lower, index - 1);
                    tmp.ubound = new Range(index + 1, tmp.upper);
                    tmp.lower = tmp.upper = index;
                }
                break;
            }
            else if (index < tmp.lower)
            {
                tmp = tmp.lbound;
            }
            else
            {
                tmp = tmp.ubound;
            }
        }
    }
    
    public static void main(String[] args) throws Exception
    {
        Scanner in = new Scanner(System.in);
        
        int n = in.nextInt();
        
        int[] idx = new int[n + 1];
        
        for (int i = 0; i < n; i++)
        {
            int a = in.nextInt();
            idx[a] = i;
        }
        
        range = new Range(0, n - 1);
        
        for (int i = 1; i <= n; i++)
        {
            calc(i, idx[i]);
        }
        
        System.out.println(sum);
    }
    
    
}