#include <bits/stdc++.h>
#pragma optimize(2)
using namespace std;

#define lc (p << 1)
#define rc (p << 1 | 1)

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

static const int K = 4;
static const int maxn = 3e5 + 10;
static const int ZERO = 3e5 + 1;
static const int oo = 0x3f3f3f3f;
int cnt[2][maxn << 1];
int a[maxn], b[maxn], sum[maxn];
int n;
struct Info {
    int ma, mi;
    int sum;

    Info() {}
    Info(int x) {
        ma = mi = x;
        sum = x;
    }
    friend Info operator+(const Info& lhs, const Info& rhs) {
        Info res;
        if (lhs.ma > rhs.ma + lhs.sum)
            res.ma = lhs.ma;
        else
            res.ma = rhs.ma + lhs.sum;

        if (lhs.mi < rhs.ma + lhs.sum)
            res.mi = lhs.mi;
        else
            res.mi = rhs.mi + lhs.sum;

        res.sum = lhs.sum + rhs.sum;
        return res;
    }
} o[maxn << 2];
void build(int p, int l, int r) {
    if (l == r) {
        o[p] = Info(l == 0 ? 0 : 1);
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    o[p] = o[lc] + o[rc];
}
void modify(int p, int l, int r, int x, int y) {
    if (l == r) {
        o[p] = Info(y);
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        modify(lc, l, mid, x, y);
    else
        modify(rc, mid + 1, r, x, y);
    o[p] = o[lc] + o[rc];
}
int query_max(int p, int l, int r, int x, int y, int pres = 0) {
    if (x <= l && r <= y) return pres + o[p].ma;
    int mid = l + r >> 1;
    int res1 = -oo, res2 = -oo;
    if (x <= mid) res1 = query_max(lc, l, mid, x, y, pres);
    if (y > mid) res2 = query_max(rc, mid + 1, r, x, y, pres + o[lc].sum);
    return max(res1, res2);
};
int query_min(int p, int l, int r, int x, int y, int pres = 0) {
    if (x <= l && r <= y) return pres + o[p].mi;
    int mid = l + r >> 1;
    int res1 = oo, res2 = oo;
    if (x <= mid) res1 = query_min(lc, l, mid, x, y, pres);
    if (y > mid) res2 = query_min(rc, mid + 1, r, x, y, pres + o[lc].sum);
    return min(res1, res2);
};
int find_first(int p, int l, int r, int x, int pres = 0) {
    if (l == r) return pres + o[p].ma == x ? l : 0;
    int mid = l + r >> 1;
    if (x >= pres + o[lc].mi && x <= pres + o[rc].ma) return find_first(lc, l, mid, x, pres);
    return find_first(rc, mid + 1, r, x, pres + o[lc].sum);
}
int find_last(int p, int l, int r, int x, int pres = 0) {
    if (l == r) return pres + o[p].ma == x ? l : n;
    int mid = l + r >> 1;
    if (x >= pres + o[lc].sum + o[rc].mi && x <= pres + o[lc].sum + o[rc].ma)
        return find_last(rc, mid + 1, r, x, pres + o[lc].sum);
    return find_last(lc, l, mid, x, pres);
}
void solve() {
    ll ans = 0;
    cin >> n;
    vector<int> a(n + 1), rnk(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        rnk[a[i]] = i;
    }
    build(1, 0, n);
    for (int i = 1; i <= n; i++) {
        b[i] = 1;
    }
    for (int _i = 1; _i <= n; _i++) {
        int i = rnk[_i];
        modify(1, 0, n, i, 0);
        b[i] = 0;
        int ma1 = query_max(1, 0, n, 0, i - 1);
        int mi1 = query_min(1, 0, n, 0, i - 1);
        int ma2 = query_max(1, 0, n, i, n);
        int mi2 = query_min(1, 0, n, i, n);
        int mi = max(mi1, mi2) - 1, ma = min(ma1, ma2) + 1;
        // cout << mi << ' ' << ma << '\n';
        int L = min(find_first(1, 0, n, mi), find_first(1, 0, n, ma));
        int R = max(find_last(1, 0, n, mi), find_last(1, 0, n, ma));
        ll res = 0;
        for (int j = L; j <= R; j++) {
            sum[j] = (j == L ? b[j] : sum[j - 1] + b[j]);
            if (j < i)
                cnt[j & 1][ZERO + sum[j]]++;
            else {
                res += cnt[j & 1][ZERO + sum[j] - 1];
                res += cnt[j & 1 ^ 1][ZERO + sum[j]];
            }
        }
        // cout << L << ' ' << R << '\n';
        ans += res * a[i];
        for (int j = L; j <= i; j++) {
            if (j < i) cnt[j & 1][ZERO + sum[j]] = 0;
        }
        modify(1, 0, n, i, -1);
        b[i] = -1;
    }
    cout << ans << '\n';
}
int main() {
    // freopen("data.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    double prev = clock();
    solve();
    double cur = clock();
    // cout << "Time=" << (cur - prev) / CLOCKS_PER_SEC << '\n';
    // cout << "tot len=" << tl << '\n';
    return 0;
}
/*
4
1 4 2 3

*/