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
import java.util.*;

public class Main {
    public void main(Scanner sc) {
        int n = sc.nextInt();
        long a[] = new long[n];

        for (int i = 0; i < n; i++) {
            a[sc.nextInt() - 1] = i;
        }

        TreeSet<Long> set = new TreeSet<>();

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long num = a[i];
            Long l = set.lower(num);
            Long r = set.higher(num);

            l = (l == null ? -1 : l);
            r = (r == null ? n : r);

            ans += (i + 1) * (num - l) * (r - num);

            set.add(num);
        }

        System.out.println(ans);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        new Main().main(sc);
        sc.close();
    }
}
