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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> v(n, 0);
    vector<int> pos(n + 1, 0);

    for(int i = 0; i < n; ++i) {
        cin >> v[i];
        pos[v[i]] = i;
    }
    
    set<int> S;
    S.insert(-1);
    S.insert(n);
    
    int64_t ans = 0;

    for(int i = 1; i <= n; ++i) {
        auto it = S.lower_bound(pos[i]);
        int right = (*it);
        it--;
        int left = (*it);
        ans += 1LL * i * (pos[i] - left) * (right - pos[i]);
        S.insert(pos[i]);
    }

    cout << ans << "\n";
}   