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>
#define ll long long
using namespace std;
const int N = 2e5+10;
int p[N];
set<pair<int,int>> s;
int main() {
	int n;
	cin >> n;
	for (int i=1;i<=n;i++) {
		int x;
		cin >> x;
		p[x] = i;
	}
	s.insert({1,n});
	ll ans = 0;
	for (int i=1;i<=n;i++) {
		auto c = --s.upper_bound({p[i],n+1});
		ans += 1ll*(p[i] - c->first + 1)*(c->second - p[i] + 1)*i;
		if (c->first != p[i]) s.insert({c->first,p[i]-1});
		if (c->second != p[i]) s.insert({p[i]+1,c->second});
		s.erase(c);
	}
	cout << ans;
	return 0;
}