#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000010,base=133;
ll n,a[N],mp[N],ans;
unsigned long long t[410][410];
unordered_map<ll,int>p;
vector<int>v[410][410];
int main () {
    freopen("sorttros.in","r",stdin);
    freopen("sorttros.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    int flag=0;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        mp[a[i]]=i;
        if (a[i]!=n-i+1) flag=1;
    }
    ll ans=n*(n-1)/2;
    if (!flag) {
        cout << ans <<endl;
    }else if (n<=400) {
        flag=0;
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n-i;j++) {
                for (int k=1;k<=n;k++) {
                    v[i][j].push_back(a[k]);
                }
                if (a[j]>a[j+1]) swap(a[j],a[j+1]);
            }
        }
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n-i;j++) {
                if (v[i][j][j-1]<v[i][j][j]) swap(v[i][j][j-1],v[i][j][j]);
                int t1=j;
                for (int i1=i;i1<=n;i1++) {
                    for (int j1=t1+1;j1<=n-i1;j1++) {
                        if (v[i][j][j1-1]>v[i][j][j1]) swap(v[i][j][j1-1],v[i][j][j1]);
                    }
                    t1=0;
                }
                for (int k=0;k<n;k++) {
                    t[i][j]=t[i][j]*base+v[i][j][k];
                }
            }
        }
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n-i;j++) {
                if (p[t[i][j]]) ans--;
                else p[t[i][j]]=1;
            }
        } 
        cout << ans <<endl;
    }else{ 
        ll t=0,mx=0;;
        flag=0;
        if (a[n]==n) {
            flag=1;
            ans-=n-3;
        }else{
            t++;
            if (mp[n]>2) {
                flag=1;
                ans-=mp[n]-3;
            }
            for (int i=mp[n]+1;i<=n-1;i++) {
                if (a[i]<a[n]) ans--;
                mx=max(mx,a[i]);
            }
            if (a[mp[n]-1]<mx) ans--;
        }
        for (int i=n-1;i>=1;i--) {
            while (a[i+t]>i) t--; 
            if (a[i+t]==i) {
                if (i>=3) {
                    if (flag) ans-=i-2;
                    else if (n>3) {
                        flag=1;
                        ans-=i-3;
                    }
                } 
            }else{
                if (mp[i]>2) {
                    if (flag) ans-=mp[i]-2;
                    else {
                        flag=1;
                        ans-=mp[i]-3;
                    }
                }
                for (int j=mp[i]+1;j<=i+t-1;j++) {
                    if (a[j]<a[i+t]&&a[j]<=i) ans--;
                    mx=max(mx,a[j]);
                }
                if (a[mp[i]-1]<mx) ans--;
                t++;
            }
        }
        cout << ans <<endl;
    }
    return 0;
}