#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[2000010];
bool flag[2000010];
int now,b1[2000010],b2[2000010];
ll ans;
int pos[2000010];
int main()
{
    freopen("sorttros.in","r",stdin);
    freopen("sorttros.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,j=n;i<=n;i++)
    {
        if(a[i]==j)
        {
            if(j!=n)
            {
                now++;
                b2[n-a[i]]++;
            }
        }
        else
        {
            if(n-a[i]-1) b1[n-a[i]-1]++;
            else now++;
            b2[n-a[i]]++;
        }
        flag[a[i]]=1;
        while(flag[j]) j--; 
    }
    for(int i=1;i<n;i++)
    {
        ans+=now;
        now-=b2[i];
        now+=b1[i];
    }
    for(int i=1;i<=n;i++) pos[a[i]]=i;
    int _ans=0;
    for(int i=n;i>2;i--)
    {
        if(pos[i]>n-i+2)
        {
            _ans=1;
            break;
        }
    }
    cout<<ans+_ans;
    return 0;
}