#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> #include <limits> using namespace std; typedef long long LL; const int MAXN=200000+1000; const int INF = numeric_limits<int>::max(); const LL LL_INF= numeric_limits<LL>::max(); #define lson L,mid,rt<<1 #define rson mid+1,R,rt<<1|1 struct Tree { LL sum; LL Ma; int flag; LL v; }tr[MAXN<<2]; void pushup(int rt){ tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum; tr[rt].Ma=max(tr[rt<<1].Ma,tr[rt<<1|1].Ma); } void pushdown(int L,int R,int rt){ if(L==R)return ; int mid=(L+R)>>1; if(tr[rt].flag){ tr[rt<<1].sum=(L-mid+1)*tr[rt].v; tr[rt<<1|1].sum=(R-(mid+1)+1)*tr[rt].v; tr[rt<<1].v=tr[rt<<1|1].v=tr[rt].v; tr[rt<<1].Ma=tr[rt<<1|1].Ma=tr[rt].v; tr[rt<<1].flag=tr[rt<<1|1].flag=1; tr[rt].flag=0; tr[rt].v=0; } } LL A[MAXN]; void build(int L,int R,int rt){ memset(&tr[rt],0,sizeof(Tree)); if(L==R){ tr[rt].sum=A[L]; tr[rt].Ma=A[L]; return ; } int mid=(L+R)>>1; build(lson);build(rson); pushup(rt); } void update(int L,int R,int rt,int l,int r,LL v){ pushdown(L,R,rt); if(l<=L&&R<=r){ tr[rt].sum=v*(R-L+1); tr[rt].v=v; tr[rt].Ma=v; tr[rt].flag=1; return ; } int mid=(L+R)>>1; if(l<=mid)update(lson,l,r,v); if(r>mid)update(rson,l,r,v); pushup(rt); } LL query(int L,int R,int rt,int l,int r,int flag){ pushdown(L,R,rt); if(l<=L&&R<=r){ if(flag==0)return tr[rt].Ma; else return tr[rt].sum; } int mid=(L+R)>>1; LL ans=0; if(l<=mid){ if(flag==0)ans=max(ans,query(lson,l,r,flag)); else ans+=query(lson,l,r,flag); } if(r>mid){ if(flag==0)ans=max(ans,query(rson,l,r,flag)); else ans+=query(rson,l,r,flag); } pushup(rt); return ans; } int resl,resr; LL queryp(int L,int R,int rt,int l,int r,LL v){ pushdown(L,R,rt); int mid=(L+R)>>1; if(l<=L&&R<=r){ if(tr[rt].Ma<=v)return -1; if(L==R)return L; if(resl!=-1&&(resr<L))return -1; resl=L;resr=R; if(tr[rt<<1].Ma>v){ return queryp(lson,l,r,v); } else return queryp(rson,l,r,v); } int ansl=-1,ansr=-1; if(l<=mid)ansl=queryp(lson,l,r,v); if(r>mid)ansr=queryp(rson,l,r,v); if(ansl==-1)return ansr; if(ansr==-1)return ansl; return min(ansl,ansr); } LL B[MAXN]; int n; int pre[MAXN],vis[MAXN]; struct node { LL val; int pos; }cs[MAXN]; int cmp(const node &x,const node &y){ if(x.val!=y.val)return x.val<y.val; return x.pos<y.pos; } int main() { while(~scanf("%d",&n)){ if(n==0)break; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)scanf("%I64d",&B[i]); LL s=0; for(int i=1;i<=n;i++){ if(B[i]<=n)vis[B[i]]=1; while(vis[s])++s; A[i]=s; } memset(pre,-1,sizeof(pre)); for(int i=1;i<=n;i++)cs[i].val=B[i],cs[i].pos=i; sort(cs+1,cs+1+n,cmp); for(int i=1;i<n;i++){ if(cs[i].val==cs[i+1].val)pre[cs[i].pos]=cs[i+1].pos; } build(1,n,1); LL ans=query(1,n,1,1,n,1); for(int i=2;i<=n;i++){ resl=resr=-1; int pos1=queryp(1,n,1,i,n,B[i-1]); int pos2=pre[i-1]; if(pos1!=-1){ if(pos2==-1){ update(1,n,1,pos1,n,B[i-1]); } else { update(1,n,1,pos1,pos2-1,B[i-1]); } } ans+=query(1,n,1,i,n,1); } printf("%I64d\n",ans); } return 0; }
|