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;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli n;
	cin>>n;
	lli place[n+1];

	for(lli i=1;i<=n;i++){
		lli a;
		cin>>a;
		place[a]=i;
	}

	lli ans=0;
	set<lli> used={0,n+1};

	for(lli i=1;i<=n;i++){
		lli r,l;

		auto itr = used.lower_bound(place[i]);
		r = *itr;

		l = *(--itr);

		ans += i*(place[i]-l)*(r-place[i]);
		used.insert(place[i]);
	}

	cout<<ans<<endl;

	return 0;
}