Given is a permutation P of \\{1, 2, \ldots, N\\}.

For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.

Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Constraints

* 2 \le N \le 10^5
* 1 \le P_i \le N
* P_i \neq P_j  (i \neq j)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
P_1 P_2 \ldots P_N


Output

Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Examples

Input

3
2 3 1


Output

5


Input

5
1 2 3 4 5


Output

30


Input

8
8 2 7 3 4 5 6 1


Output

136
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
int n,x,w[100010],le[100010],ho[100010];
ll ans;
int main(){
	read(n);
	for (int i=1;i<=n;i++){read(x);w[x]=i;}
	for (int i=1;i<=n;i++)le[i]=i-1,ho[i]=i+1;
	for (int i=1;i<=n;i++){
		int x=le[w[i]],y=le[x];
		int z=ho[w[i]],p=ho[z];
		if (x!=0)ans+=1ll*(x-y)*(z-w[i])*i;
		if (z!=n+1)ans+=1ll*(w[i]-x)*(p-z)*i;
		ho[x]=z;le[z]=x;
	}
	cout<<ans<<endl;
	return 0;
}