#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <typename T> bool chmin(T &a, const T &b) {
if (a <= b) return false;
a = b;
return true;
}
template <typename T> bool chmax(T &a, const T &b) {
if (a >= b) return false;
a = b;
return true;
}
using namespace std;
vector<int> random_permutation(int n){
random_device seed_gen;
mt19937 engine(seed_gen());
vector<int> p(n);
iota(p.begin(), p.end(), 1);
shuffle(p.begin(), p.end(), engine);
return p;
}
ll naive(int n, vector<int> p){
ll ans = 0;
rep(i,0,n){
priority_queue<int, vector<int>, greater<int>> larger;
priority_queue<int> smaller;
rep(j,i,n){
if (smaller.empty()){
smaller.push(p[j]);
}else if(larger.empty()){
smaller.push(p[j]);
}else if(larger.top() > p[j]){
smaller.push(p[j]);
}else{
larger.push(p[j]);
}
while ((int)smaller.size() < (int)larger.size()){
smaller.push(larger.top());
larger.pop();
}
while ((int)smaller.size() > (int)larger.size() + 1){
larger.push(smaller.top());
smaller.pop();
}
ans += smaller.top();
}
}
return ans;
}
const int mx = 800;
ll fast(int n, vector<int> p){
ll ans = 0;
vector<int> left(2 * mx + 1);
vector<int> right(2 * mx + 1);
rep(i,0,n){
fill(left.begin(), left.end(), 0);
fill(right.begin(), right.end(), 0);
int targ = p[i];
{
int cnt = mx;
left[cnt]++;
rrep(j,0,i){
if (targ < p[j]) cnt--;
else cnt++;
if (abs(cnt - mx) > mx) break;
left[cnt]++;
}
}
{
int cnt = mx + 1;
right[cnt]++;
rep(j,i+1,n){
if (targ < p[j]) cnt--;
else cnt++;
if (abs(cnt - mx) > mx) break;
right[cnt]++;
}
}
ll var = 0;
rep(j, 0, 2 * mx){
var += (ll)right[2 * mx - j] * (left[j] + left[j + 1]);
}
ans += var * targ;
}
return ans;
}
ll fast2(int n, vector<int> p){
ll ans = 0;
vector<int> left(2 * mx + 1);
vector<int> right(2 * mx + 1);
vector<int> a(n, +1);
vector<int> q(n);
rep(i,0,n){
q[p[i] - 1] = i;
}
reverse(q.begin(), q.end());
for (int i: q){
fill(left.begin(), left.end(), 0);
fill(right.begin(), right.end(), 0);
{
int cnt = mx;
left[cnt]++;
rrep(j,0,i){
cnt += a[j];
if (abs(cnt - mx) > mx) break;
left[cnt]++;
}
}
{
int cnt = mx + 1;
right[cnt]++;
rep(j,i+1,n){
cnt += a[j];
if (abs(cnt - mx) > mx) break;
right[cnt]++;
}
}
ll var = 0;
rep(j, 0, 2 * mx){
var += (ll)right[2 * mx - j] * (left[j] + left[j + 1]);
}
ans += var * p[i];
a[i] = -1;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//*
int n; cin >> n;
vector<int> p(n);
rep(i,0,n){
cin >> p[i];
}
//*/
/*
int n = 300000;
vector<int> p = random_permutation(n);
//*/
//cout << naive(n, p) << endl;
cout << fast2(n, p) << endl;
//cout << fast(n, p) << endl;
}