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

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

using ll = long long;

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;
        res.ma = max(lhs.ma, rhs.ma + lhs.sum);
        res.mi = min(lhs.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) {
        assert(pres + o[p].ma == x);
        return l;
    }
    int mid = l + r >> 1;
    if (x >= pres + o[lc].mi && x <= pres + o[lc].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) {
        assert(pres + o[p].ma == x);
        return l;
    }
    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 print(int p, int l, int r, int pres = 0) {
    if (l == r) {
        cout << pres + o[p].ma << ' ';
        return;
    }
    int mid = l + r >> 1;
    print(lc, l, mid, pres);
    print(rc, mid + 1, r, pres + o[lc].sum);
}
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), ma = min(ma1, ma2);
        // print(1, 0, n);
        // cout << '\n';
        // 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));
        L = max(0, L - 1);
        R = min(n, R + 1);
        if (L <= R) {
            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 << i << ": " << 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';
    return 0;
}
/*
4
1 4 2 3

20
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20

10
1 2 3 4 5 6 7 8 9 10
*/