const int N=2e5+5;

int n;
int a[N];
int cntl[N],cntr[N];

struct node{
    int cnt[2];
    ll val[2][2];
}dat[N<<2];
node merge(node a,node b){
    node c;
    c.cnt[0]=a.cnt[0]+b.cnt[0],c.cnt[1]=a.cnt[1]+b.cnt[1];
    rep(i,0,1)rep(j,0,1){
        if(b.cnt[i]){
            c.val[i][j]=INF;
            if(a.cnt[0])chmin(c.val[i][j],b.val[i][0]+a.val[0][j]);
            if(a.cnt[1])chmin(c.val[i][j],b.val[i][1]+a.val[1][j]);
            if(!a.cnt[j])chmin(c.val[i][j],b.val[i][j]);
        }else c.val[i][j]=a.val[i][j];
    }
    return c;
}
void build(int x=1,int l=1,int r=n){
    if(l==r){
        dat[x].cnt[0]=cntl[l];
        dat[x].cnt[1]=cntr[l];
        dat[x].val[0][0]=dat[x].val[0][1]=!!cntl[l];
        dat[x].val[1][0]=dat[x].val[1][1]=!!cntr[l];
        return;
    }
    int m=l+r>>1;
    build(x<<1,l,m),build(x<<1|1,m+1,r);
    dat[x]=merge(dat[x<<1],dat[x<<1|1]);
}
void update(int k,int x=1,int l=1,int r=n){
    if(!k)return;
    if(l==r){
        dat[x].cnt[0]=cntl[l];
        dat[x].cnt[1]=cntr[l];
        dat[x].val[0][0]=dat[x].val[0][1]=!!cntl[l];
        dat[x].val[1][0]=dat[x].val[1][1]=!!cntr[l];
        return;
    }
    int m=l+r>>1;
    if(k<=m)update(k,x<<1,l,m);
    else update(k,x<<1|1,m+1,r);
    dat[x]=merge(dat[x<<1],dat[x<<1|1]);
}
node query(int lq,int rq,int x=1,int l=1,int r=n){
    if(lq>rq)return node();
    if(lq<=l&&r<=rq)return dat[x];
    int m=l+r>>1;
    if(rq<=m)return query(lq,rq,x<<1,l,m);
    if(m<lq)return query(lq,rq,x<<1|1,m+1,r);
    return merge(query(lq,rq,x<<1,l,m),query(lq,rq,x<<1|1,m+1,r));
}

inline void Main(){
	cin>>n;
    rep(i,1,n)cin>>a[i],++cntr[a[i]];
    build();
    ll ans=0;
    rep(i,1,n){
        --cntr[a[i]],++cntl[a[i-1]];
        update(a[i]),update(a[i-1]);
        if(!a[i])continue;
        node res=query(1,a[i]-1);
        ans+=min({res.val[0][0],res.val[0][1],res.val[1][0],res.val[1][1]})+1;
    }
    put(ans);
}