/*首先预处理好f g数组 fi :以a[i]为结尾的 最长上升子序列的长度 gi :以a[i]为开始的 最长上升子序列的长度 mxx : 最长上升子序列的长度 线段树优化 nlogn(不包含a[i]==0)显然把所有0换成x  只可能是mxx变成mxx+1  然后我们考虑一对 i j (下标) 若 f[i]+g[j]==mxx 则 所有a[i]+1~~~a[j]-1之间的x  他们对用的lis长度为mxx+1  然后枚举i j凉了 对于一个i 我们只需要找到 他后面的 一个j 满足  f[i]+g[j]==mxx 并且a[j]最大 然后维护bg[i] 表示长度为g[j]==i的所有的 a[j]中最大的  从后往前枚举i 然后维护 bg O(1)转移  上述过程可能 i和bg维护的j之间 他没有0 那就不能转移 所以 按0分段  遇到0 就把之前的信息更新bg   然后没了   */#include
     
      #include
      
       #include
       
        #define lc k*2#define rc k*2+1#define mid (l+r)/2#define maxn 400010#define ll long longusing namespace std;ll n,a[maxn],f[maxn],s[maxn],g[maxn],as[maxn],bg[maxn],c[maxn][2];void Insert(ll k,ll l,ll r,ll x,ll y){    if(x==l&&r==x){        s[k]=max(s[k],y);return;    }    if(x<=mid)Insert(lc,l,mid,x,y);    else Insert(rc,mid+1,r,x,y);    s[k]=max(s[lc],s[rc]);}ll Query(ll k,ll l,ll r,ll x,ll y){    if(x>y)return 0;    if(x<=l&&y>=r)return s[k];    ll res=0;    if(x<=mid)res=max(res,Query(lc,l,mid,x,y));    if(y>mid)res=max(res,Query(rc,mid+1,r,x,y));    return res;}int main(){    while(~scanf("%lld",&n)){        for(ll i=0;i<=n*4;i++)            s[i]=f[i]=g[i]=as[i]=0;        for(ll i=1;i<=n;i++){            scanf("%lld",&a[i]);            //a[i]=rand();            f[i]=1;g[i]=1;        }        ll mxx=1;        for(ll i=1;i<=n;i++){            if(a[i]==0)continue;            ll mx=Query(1,1,n,1,a[i]-1);            f[i]=mx+1;mxx=max(mxx,f[i]);            Insert(1,1,n,a[i],f[i]);        }        for(ll i=0;i<=n*4;i++)s[i]=0;        for(ll i=n;i>=1;i--){            if(a[i]==0)continue;            ll mx=Query(1,1,n,a[i]+1,n);            g[i]=mx+1;Insert(1,1,n,a[i],g[i]);        }        for(ll i=0;i<=n*4;i++)bg[i]=0;        ll cnt=0;a[0]=-1;        for(ll i=n;i>=0;i--){            if(a[i]==0){                for(ll j=1;j<=cnt;j++)                    bg[c[j][0]]=max(bg[c[j][0]],c[j][1]);                cnt=0;bg[0]=n+1;            }            else{                ll mx=bg[mxx-f[i]];                c[++cnt][0]=g[i];c[cnt][1]=a[i];                if(mx-1
        
         0)ans+=i*(mxx+1);            else ans+=i*mxx;            //("%lld\n",ans);        }        printf("%lld\n",ans);    }    return 0;}