3250 BadHairDay

（id:Respect2Dさんの方が圧倒的に頭がいい解法です）
なぜかsegtree解法しか思いつかなかった。最初はO(Nlog^2n)でやろうと思ったけど
TLEで死亡しそうだったので多少工夫
もし左のノードみてあったらそれをすぐ返してしまえーというだけの話だけど

struct segtree{
	vi val;
	int n,ownn;
	int qtall;
	segtree(int n_){
		n=1;
		ownn=n_;
		while(n<n_) n*=2;
		val.resize(n*2);
	}
	void add(int k,int a){
		k+=n-1;
		val[k]+=a;
		while(k){
			k=(k-1)/2;
			val[k]=max(val[k*2+1],val[k*2+2]);
		}
	}
	int q(int a,int b,int node,int l,int r){
		if(val[node]<qtall) return -1;
		if(a<=l && r<=b){
			if(node>=n-1){
				return node-n+1;
			}
			int md=(l+r)/2;
			if(val[node*2+1]>=qtall) return q(a,b,node*2+1,l,md);
			return q(a,b,node*2+2,md,r);
		}
		if(r<=a || b<=l) return -1;
		int md=(l+r)/2;
		int left=q(a,b,node*2+1,l,md);
		if(left!=-1) return left;
		return q(a,b,node*2+2,md,r);
	}		
	int query(int a){
		qtall=val[a+n-1];
		int val=q(a+1,n,0,0,n);
		if(val==-1) return ownn-a-1;
		return val-a-1;
	}
};


int main(){
	int n;scanf("%d",&n);
	segtree seg(n);
	REP(i,n){
		int t;scanf("%d",&t);
		seg.add(i,t);
	}
	lint res=0;
	REP(i,n){
		res+=seg.query(i);
	}
	printf("%lld\n",res);
	return 0;
}