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

#define V vector
#define pb push_back
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
#define fi first
#define se second

typedef long long LL;
typedef pair<int, int> pi;

const int INF = 2e9 + 10000;

mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());

void solve() {
    int n;
    cin >> n;
    V<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    int base = n;
    V<int> tab(base * 2 + 1);
    const int T = 20;
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        int len = T * (n / (abs(a[i] - n / 2) + 1));
        int l = max(1, i - len), r = min(n, i + len);
        int mn = INF, mx = -INF;
        int cur = 0;
        for (int j = i; j >= l; j--) {
            mn = min(mn, cur), mx = max(mx, cur);
            tab[base + cur]++;
            if (j == l) break;
            if (a[j - 1] > a[i]) cur++;
            else cur--;
        }
        cur = 0;
        for (int j = i; j <= r; j++) {
            ans += 1LL * tab[base - cur] * a[i];
            ans += 1LL * tab[base - cur + 1] * a[i];
            if (j == r) break;
            if (a[j + 1] > a[i]) cur++;
            else cur--;
        }
        for (int i = mn; i <= mx; i++) {
            tab[i + base] = 0;
        }
    }
    cout << ans << endl;
}

int main() {

    ios::sync_with_stdio(0), cin.tie(0);
    // int t;
    // cin >> t;
    // while (t--)
    solve();
}