The Kingdom of Kremland is a tree (a connected undirected graph without cycles) consisting of n vertices. Each vertex i has its own value a_i. All vertices are connected in series by edges. Formally, for every 1 ≤ i < n there is an edge between the vertices of i and i+1.

Denote the function f(l, r), which takes two integers l and r (l ≤ r):

  * We leave in the tree only vertices whose values ​​range from l to r. 
  * The value of the function will be the number of connected components in the new graph. 



Your task is to calculate the following sum: $$$∑_{l=1}^{n} ∑_{r=l}^{n} f(l, r) $$$

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of vertices in the tree.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the values of the vertices.

Output

Print one number — the answer to the problem.

Examples

Input


3
2 1 3


Output


7

Input


4
2 1 1 3


Output


11

Input


10
1 5 2 5 5 3 10 6 5 1


Output


104

Note

In the first example, the function values ​​will be as follows: 

  * f(1, 1)=1 (there is only a vertex with the number 2, which forms one component) 
  * f(1, 2)=1 (there are vertices 1 and 2 that form one component) 
  * f(1, 3)=1 (all vertices remain, one component is obtained) 
  * f(2, 2)=1 (only vertex number 1) 
  * f(2, 3)=2 (there are vertices 1 and 3 that form two components) 
  * f(3, 3)=1 (only vertex 3) 

Totally out 7.

In the second example, the function values ​​will be as follows: 

  * f(1, 1)=1 
  * f(1, 2)=1 
  * f(1, 3)=1 
  * f(1, 4)=1 
  * f(2, 2)=1 
  * f(2, 3)=2 
  * f(2, 4)=2 
  * f(3, 3)=1 
  * f(3, 4)=1 
  * f(4, 4)=0 (there is no vertex left, so the number of components is 0) 

Totally out 11.
#include <bits/stdc++.h>
#include <iomanip>

#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DECIMAL(n)  std::cout << std::fixed;std::cout << std::setprecision(n);
#define hell 1000000007
#define PI 3.14159265358979323844
#define mp make_pair
#define pb push_back
#define fi first 
#define se second
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))  
#define REVERSE(v) reverse(ALL(v))
#define endl "\n"
#define maxc(v) max_element(all(v))
#define minc(v) min_element(all(v))
#define GCD(m,n) __gcd(m,n)
#define LCM(m,n) m*(n/GCD(m,n))
#define inputarr(a,n) for(int i=0;i<n;++i) cin>>a[i]
#define initarr(a,n,x) for (int i=0;i<n;++i) a[i]=x
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define sz(a) (int)a.size()
#define sl(a) (int)a.length()
#define invect(data,n,commands) for(int i = 0;i<n;i++){int tmp;cin>>tmp;data.pb(tmp);commands}
#define inset(data,n,commands) for(int i = 0;i<n;i++){int tmp;cin>>tmp;data.insert(tmp);commands}
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

#define ll long long
#define ld long double 
#define pii std::pair<int, int> 
#define pll std::pair<ll, ll>  
#define vi vector<int>  
#define vvi vector<vi > 
#define vii vector<pii >

pii operator+(pii a, pii b)
{
	return {a.fi+b.fi,a.se+b.se};
}
pll operator+(pll a, pll b)
{
	return {a.fi+b.fi,a.se+b.se};
}
std::ostream& operator<<(std::ostream& out,pii a)
{
	out<<a.fi<<" "<<a.se<<endl;
	return out;
}
std::ostream& operator<<(std::ostream& out,pll a)
{
	out<<a.fi<<" "<<a.se<<endl;
	return out;
}
std::istream& operator>>(std::istream& in,pii &a)
{
    in>>a.fi>>a.se;
    return in;
}
std::istream& operator>>(std::istream& in,pll &a)
{
    in>>a.fi>>a.se;
    return in;
}

using namespace std;

int main()
{
    FAST;
    int n;
    cin>>n;
    ll int a[n];
    inputarr(a,n);
    if(n==1)
    {
    	cout<<1;
    	return 0;
    }
    ll dp[n]={0};
    vii poss[n+1];
    for (int i = 0; i < n; ++i)
    {
    	if(i==0)
    	{
    		poss[a[i]].pb({hell,a[i+1]});
    	}else if(i==n-1)
    	{
    		poss[a[i]].pb({a[i-1],hell});
    	}else{
    		poss[a[i]].pb({a[i-1],a[i+1]});
    	}
    }
    trav(i,poss[1])
    {
    	if(i.fi!=1)
    		++dp[0];
    	if(i.se!=1)
    		++dp[0];
    }
    vii pos[n+1];
    for (int i = 0; i < n+1; ++i)
    {
    	int l,r;
    	trav(j,poss[i])
    	{
    		if(j.fi!=i&&j.se!=i)
    			pos[i].pb(j);
    		else if(j.fi!=i&&j.se==i)
    			l=j.fi;
    		else if(j.fi==i&&j.se!=i)
    			{r=j.se;pos[i].pb({l,r});}
    	}
    }
    dp[0]/=2;
    for (int i = 1; i < n; ++i)
    {
    	trav(j,poss[i+1])
    	{
    		if(j.fi!=(i+1))
    			++dp[i];
    		if(j.se!=(i+1))
    			++dp[i];
    	}
    	dp[i]/=2;
    	dp[i]+=dp[i-1];
    	trav(j,pos[i+1])
    	{
    		int l=j.fi,r=j.se;
    		int x=min(l,r);
    		int y=l;
    		if(l==hell)
    			y=r;
    		else if(r!=hell)
    			y=max(r,y);
    		if(x<i+1)
    		{
    			int kk=hell;
    			if(l<hell&&(i-l)>0)
    				kk=i-l;
    			if(r<hell&&(i-r)>=0)
    				kk=min(kk,i-r);
    			dp[i]+=kk;
    		}else{
    			dp[i]+=i;
    		}
    		if(l<(i+1)&&r<(i+1))
    		{
    			dp[i]-=x;
    		}
    	}
    }
    ll ans=0;
    for (int i = 0; i < n; ++i)
    {
    	ans+=dp[i];
    }
    cout<<ans;
}