#include<bits/stdc++.h>
#define int long long
#define lson num * 2
#define rson num * 2 + 1
#define M ((L + R)>>1)
using namespace std;
const int N = 2e6 + 5;


struct tree{
    int l,r,maxn;
}tr[N * 4] ;

int n,ans = 0,flag = 1;
int t[N],g[N];

void build(int num,int L,int R){
    tr[num].l = L;tr[num].r = R;tr[num].maxn = 0;
    if(L == R) return;
    build(lson,L,M);build(rson,M + 1,R);
}

void add(int num,int x,int k){
    tr[num].maxn = k;
    if(tr[num].l == tr[num].r) return;
    if(x <= tr[lson].r) add(lson,x,k);
    else add(rson,x,k);
}

int ask(int num,int x,int y){
    if(tr[num].l >= x && tr[num].r <= y) return tr[num].maxn;
    int res = 0;
    if(x <= tr[lson].r) res = ask(lson,x,y);
    if(y >= tr[rson].l) res = max(res,ask(rson,x,y));
    return res;
}

int c[N];
void add1(int x){
    while(x <= n) {
        c[x]++;
        x += (x & -x);
    }
}

int ask1(int x){
    int ssum = 0;
    while(x){
        ssum += c[x];
        x -= (x & -x);
    }
    return ssum;
}


signed main()
{
    freopen("sorttros.in","r",stdin);
    freopen("sorttros.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;build(1,1,n);
    
    int xx;
    for(int i = 1;i <= n;i++) cin>>xx,t[xx] = i;
    
    
    for(int i = 1;i <= n;i++){
        add(1,t[i],i);add1(t[i]);if(ask1(t[i]) == 3 && flag) ans++,flag = 0;
        if(t[i] != n){
            int k = ask(1,t[i] + 1,n);
            if(k) g[i] = g[k] + 1;
        }
        if(t[i] != 1){
            int k = ask(1,1,t[i] - 1);
            if(k) ans++;
        }
    }
    
    int top = 0;
    for(int i = n;i >= 1;i--){
        if(t[i] > t[top]) top = i;
        ans += g[top];
    }
    
    cout<<ans<<'\n';
    return 0;
}