#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 3e5 + 5;
const int M = 900;
int A[MAXN],pos[MAXN],cnt[(MAXN << 1) + 10],n,v[MAXN];
ll res;
int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&A[i]);
        pos[A[i]] = i;
        v[i] = -1;
    }


    for(int i = n; i >= 1; --i)
    {
        int cur = M;
        for(int j = 0; j <= M * 2; ++j) cnt[j] = 0;
        cnt[M] = 1; v[pos[i]] = 1;
        for(int j = pos[i] - 1; j >= 1; --j)
        {
            cur += v[j];
            if(cur > (M << 1) || cur < 0) break;
            cnt[cur]++;
        }
        cur = M;
        for(int j = pos[i]; j <= n; ++j)
        {
            cur += v[j];
            if(cur > (M << 1) || cur < 0) break;
            res += 1ll * i * (cnt[2 * M - cur + 1] + cnt[2 * M - cur + 2]);
        }
    }
    printf("%lld\n",res);
}