#include <bits/stdc++.h>
using namespace std;


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

static const int K = 100;
static const int maxn = 3e5 + 10;
static const int ZERO = 3e5 + 1;
int cntr[2][maxn << 1];

void solve() {
    ll ans = 0;
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        // for (int i = -n; i <= n; i++) {
        //     cout << cntr[0][ZERO + i] << ' ';
        // }
        // cout << '\n';
        int r = 1;
        int lsum = 0, rsum = 0;
        ll res = 0;
        cntr[i & 1][ZERO]++;
        while (abs(lsum - rsum) < K && r < max(i, n - i + 1)) {
            r++;
            if (i - r + 1 >= 1) {
                lsum += (a[i - r + 1] > a[i] ? 1 : -1);
            }
            if (i + r - 1 <= n) {
                rsum += (a[i + r - 1] > a[i] ? 1 : -1);
                cntr[(i + r - 1) & 1][ZERO + rsum]++;
            }
        }
        int L = max(1, i - r + 1), R = min(n, i + r - 1);
        // cout << L << ' ' << R << ' ' << lsum << ' ' << rsum << '\n';
        while (L <= i) {
            res += ll(a[i]) * cntr[L & 1][ZERO - lsum];
            res += ll(a[i]) * cntr[(L & 1) ^ 1][ZERO - lsum + 1];
            lsum -= (a[L] > a[i] ? 1 : -1);
            L++;
        }
        while (R >= i) {
            cntr[R & 1][ZERO + rsum]--;
            rsum -= (a[R] > a[i] ? 1 : -1);
            R--;
        }
        // cout << res << '\n';
        ans += res;
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);

    int T = 1;
    while (T--)
        solve();

    return 0;
}
/*
4
1 4 2 3
*/