#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 300005;
const int B = 25;

#define lson (x << 1)
#define rson ((x << 1) | 1)

struct node{
    pair <int,int> mx[B + 5];
    pair <int,int> mi[B + 5];
}t[N << 2];
int tag[N << 2];

node merge(node nx,node ny){
    node ret;
    int cx = 1,cy = 1;
    for(int i = 1;i <= B;i ++){
        if(nx.mx[cx].first == ny.mx[cy].first){
            ret.mx[i] = make_pair(nx.mx[cx].first,nx.mx[cx].second + ny.mx[cy].second);
            cx ++; cy ++;
        }
        else if(nx.mx[cx].first > ny.mx[cy].first) ret.mx[i] = nx.mx[cx ++];
        else ret.mx[i] = ny.mx[cy ++];
    }
    cx = cy = 1;
    for(int i = 1;i <= B;i ++){
        if(nx.mi[cx].first == ny.mi[cy].first){
            ret.mi[i] = make_pair(nx.mi[cx].first,nx.mi[cx].second + ny.mi[cy].second);
            cx ++; cy ++;
        }
        else if(nx.mi[cx].first < ny.mi[cy].first) ret.mi[i] = nx.mi[cx ++];
        else ret.mi[i] = ny.mi[cy ++];
    }
    return ret;
}

void pushup(int x){
    t[x] = merge(t[lson],t[rson]);
}

void apply(int x,int v){
    for(int i = 1;i <= B;i ++){
        if(t[x].mx[i].first > -INF) t[x].mx[i].first += v;
        if(t[x].mi[i].first < INF) t[x].mi[i].first += v;
    }
}

void pushdown(int x){
    if(tag[x]){
        apply(lson,tag[x]); tag[lson] += tag[x];
        apply(rson,tag[x]); tag[rson] += tag[x];
        tag[x] = 0;
    }
}

void build(int x,int l,int r){
    tag[x] = 0;
    if(l == r){
        for(int i = 1;i <= B;i ++){
            t[x].mx[i] = make_pair(-INF,0);
            t[x].mi[i] = make_pair(INF,0);
        }
        t[x].mx[1] = t[x].mi[1] = make_pair(0,1);
        return;
    }
    int mid = (l + r) >> 1;
    build(lson,l,mid);
    build(rson,mid + 1,r);
    pushup(x);
}

node query(int x,int l,int r,int L,int R){
    if(L <= l && r <= R) return t[x];
    int mid = (l + r) >> 1;
    pushdown(x);
    if(L <= mid && R <= mid) return query(lson,l,mid,L,R);
    if(L > mid && R > mid) return query(rson,mid + 1,r,L,R);
    return merge(query(lson,l,mid,L,R),query(rson,mid + 1,r,L,R));
}

void modify(int x,int l,int r,int L,int R,int v){
    if(L <= l && r <= R){
        apply(x,v); tag[x] += v;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(x);
    if(L <= mid) modify(lson,l,mid,L,R,v);
    if(R > mid) modify(rson,mid + 1,r,L,R,v);
    pushup(x);
}

int a[N],pos[N];

void solve(){
    ll ans = 0; int n;
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        pos[a[i]] = i;
    }
    build(1,1,n);
    for(int i = 1;i <= n;i ++) modify(1,1,n,pos[i],n,1);
    for(int i = 1;i <= n;i ++){
        if(i > 1) modify(1,1,n,pos[i - 1],n,-1);
        modify(1,1,n,pos[i],n,-1);
        int pren = query(1,1,n,pos[i],pos[i]).mx[1].first;
        unordered_map <int,int> mp,vis; node nl;
        if(pos[i] > 1){
            nl = query(1,1,n,1,pos[i] - 1);
            for(int j = 1;j <= B;j ++){
                if(nl.mi[j].first != INF && mp.find(pren - nl.mi[j].first) == mp.end()) mp[pren - nl.mi[j].first] = nl.mi[j].second;
                if(nl.mx[j].first != -INF && mp.find(pren - nl.mx[j].first) == mp.end()) mp[pren - nl.mx[j].first] = nl.mx[j].second;
            }
        }
        mp[pren - 0] ++; // 0, [1...pos_i]
        nl = query(1,1,n,pos[i],n);
        ll cnt = 0;
        for(int j = 1;j <= B;j ++){
            if(nl.mi[j].first != INF && vis.find(nl.mi[j].first) == vis.end()){
                cnt += 1ll * nl.mi[j].second * mp[pren - nl.mi[j].first];
                vis[nl.mi[j].first] = 1;
            }
            if(nl.mx[j].first != -INF && vis.find(nl.mx[j].first) == vis.end()){
                cnt += 1ll * nl.mx[j].second * mp[pren - nl.mx[j].first];
                vis[nl.mx[j].first] = 1;
            }
        }
        ans += cnt * i;
        // cout << i << ' ' << cnt << ' ' << ans << endl;
    }

    build(1,1,n);
    for(int i = 1;i <= n;i ++) modify(1,1,n,pos[i],n,1);
    for(int i = 1;i <= n;i ++){
        modify(1,1,n,pos[i],n,-2);
        int pren = query(1,1,n,pos[i],pos[i]).mx[1].first;
        unordered_map <int,int> mp,vis; node nl;
        if(pos[i] > 1){
            nl = query(1,1,n,1,pos[i] - 1);
            for(int j = 1;j <= B;j ++){
                // cout << nl.mi[j].first << ',' << nl.mi[j].second << ' ' << nl.mx[j].first << ',' << nl.mx[j].second << ';';
                if(nl.mi[j].first != INF && mp.find(pren - nl.mi[j].first) == mp.end()) mp[pren - nl.mi[j].first] = nl.mi[j].second;
                if(nl.mx[j].first != -INF && mp.find(pren - nl.mx[j].first) == mp.end()) mp[pren - nl.mx[j].first] = nl.mx[j].second;
            }
        }
        mp[pren - 0] ++; // 0, [1...pos_i]
        nl = query(1,1,n,pos[i],n);
        ll cnt = 0;
        for(int j = 1;j <= B;j ++){
            if(nl.mi[j].first != INF && vis.find(nl.mi[j].first) == vis.end()){
                cnt += 1ll * nl.mi[j].second * mp[pren - nl.mi[j].first];
                vis[nl.mi[j].first] = 1;
            }
            if(nl.mx[j].first != -INF && vis.find(nl.mx[j].first) == vis.end()){
                cnt += 1ll * nl.mx[j].second * mp[pren - nl.mx[j].first];
                vis[nl.mx[j].first] = 1;
            }
        }
        ans += cnt * i;
        // cout << i << ',' << cnt << ' ' << ans << endl;
    }

    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    solve();
    return 0;
}