#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int MAX_N = 300000 + 5;
const int MAX_M = 600 + 5;
const int K = 20;
const int BS = 503;
const int INF32 = 0x3f3f3f3f;

int N, a[MAX_N], pos[MAX_N], lazy[MAX_M], sum[MAX_N];
unordered_multiset <int> s[MAX_M];
struct SegmentNode{
    int minv, maxv, lazy;
}node[1 << 20];

void segment_build(int i, int l, int r) {
    node[i].lazy = 0;
    node[i].minv = l;
    node[i].maxv = r;
    if (l == r) return ;
    int mid = l + r >> 1;
    segment_build(i << 1, l, mid);
    segment_build(i << 1 | 1, mid + 1, r);
}

void segment_modify(int i, int l, int r, int ql, int qr, int v) {
    if (l < ql || r > qr) {
        int mid = l + r >> 1;
        if (ql <= mid) segment_modify(i << 1, l, mid, ql, qr, v);
        if (mid < qr) segment_modify(i << 1 | 1, mid + 1, r, ql, qr, v);
        node[i].minv = min(node[i << 1].minv, node[i << 1 | 1].minv) + node[i].lazy;
        node[i].maxv = max(node[i << 1].maxv, node[i << 1 | 1].maxv) + node[i].lazy;
    }else {
        node[i].minv += v;
        node[i].maxv += v;
        node[i].lazy += v;
    }
}

pii segment_query(int i, int l, int r, int ql, int qr) {
    if (l < ql || r > qr) {
        int mid = l + r >> 1, minv = INF32, maxv = -INF32;
        if (ql <= mid) {
            auto [m, M] = segment_query(i << 1, l, mid, ql, qr);
            minv = min(minv, m); maxv = max(maxv, M);
        }
        if (mid < qr) {
            auto [m, M] = segment_query(i << 1 | 1, mid + 1, r, ql, qr);
            minv = min(minv, m); maxv = max(maxv, M);
        }
        return pair(minv + node[i].lazy, maxv + node[i].lazy);
    }else {
        return pair(node[i].minv, node[i].maxv);
    }
}

int segment_findl(int i, int l, int r, int ql, int qr, int vl, int vr, int sum = 0) {
    if (min(vr, node[i].maxv + sum) < max(vl, node[i].minv + sum)) return -1;
    if (i < ql || r > qr) {
        int mid = l + r >> 1, p = -1; sum += node[i].lazy;
        if (ql <= mid) p = segment_findl(i << 1, l, mid, ql, qr, vl, vr, sum);
        if (p != -1) return p;
        if (mid < qr) p = segment_findl(i << 1 | 1, mid + 1, r, ql, qr, vl, vr, sum);
        return p;
    }
    while (l < r) {
        int mid = l + r >> 1;
        sum += node[i].lazy;
        if (min(vr, node[i << 1].maxv + sum) < max(vl, node[i << 1].minv + sum)) {
            l = mid + 1; i = i << 1 | 1;
        }else {
            r = mid; i <<= 1;
        }
    }
    assert(vl <= node[i].minv + sum && node[i].minv + sum <= vr);
    return l;
}

int segment_findr(int i, int l, int r, int ql, int qr, int vl, int vr, int sum = 0) {
    if (min(vr, node[i].maxv + sum) < max(vl, node[i].minv + sum)) return -1;
    if (i < ql || r > qr) {
        int mid = l + r >> 1, p = -1; sum += node[i].lazy;
        if (mid < qr) p = segment_findr(i << 1 | 1, mid + 1, r, ql, qr, vl, vr, sum);
        if (p != -1) return p;
        if (ql <= mid) p = segment_findr(i << 1, l, mid, ql, qr, vl, vr, sum);
        return p;
    }
    while (l < r) {
        int mid = l + r >> 1;
        sum += node[i].lazy;
        if (min(vr, node[i << 1 | 1].maxv + sum) < max(vl, node[i << 1 | 1].minv + sum)) {
            r = mid; i <<= 1;
        }else {
            l = mid + 1; i = i << 1 | 1;
        }
    }
    assert(vl <= node[i].minv + sum && node[i].minv + sum <= vr);
    return l;
}

void modify(int l) {
    segment_modify(1, 0, N, l, N, -1);
}

ll solve(int mid, int l, int r) {
    static int cntl[MAX_N << 1], cntr[MAX_N << 1];
    int minv = N + 1, maxv = -N - 1;
    for (int i = mid, j = 0; i >= l; i --) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntl[j + MAX_N] ++;
        minv = min(minv, j);
        maxv = max(maxv, j);
    }
    for (int i = mid, j = 0; i <= r; i ++) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntr[j + MAX_N] ++;
    }
    ll ans = 0;
    for (int i = minv; i <= maxv; i ++) {
        ans += 1ll * cntl[i + MAX_N] * (cntr[MAX_N - i] + cntr[MAX_N - i + 1]);
    }
    for (int i = mid, j = 0; i >= l; i --) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntl[j + MAX_N] = 0;
    }
    for (int i = mid, j = 0; i <= r; i ++) {
        if (a[i] < a[mid]) j --;
        else if (a[i] > a[mid]) j ++;
        cntr[j + MAX_N] = 0;
    }
    return ans * a[mid];
}

ll query(int mid) {
    auto [lm, lM] = segment_query(1, 0, N, 0, mid - 1);
    auto [rm, rM] = segment_query(1, 0, N, mid, N);
    int ll = max(lm, rm - 1), lr = min(lM, rM);
    int rl = max(rm, lm), rr = min(rM, lM + 1);
    if (lr < ll || rr < rl) assert(false);
    int lp = segment_findl(1, 0, N, 0, mid - 1, ll, lr) + 1;
    int rp = segment_findr(1, 0, N, mid, N, rl, rr);
    return solve(mid, lp, rp);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for (int i = 1; i <= N; i ++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    segment_build(1, 0, N);
    ll ans = 0;
    for (int i = 1; i <= N; i ++) {
        modify(pos[i]);
        if (i > 1) modify(pos[i - 1]);
        ans += query(pos[i]);
    }
    cout << ans << '\n';
    cerr << "time : " << clock() << endl;
    
    return 0;
}