线性做法WA1 2 6 7 8 13

inline void findl(int xx)
{
	int ll=1,rr=xx,mid,ans=9999999;
	while(ll<=rr)
	{
		mid=(ll+rr)>>1;
		if(x[mid]<x[xx]-r[xx])
			ll=mid+1;
		else{rr=mid-1;ans=min(ans,m[mid].l);}
		}	
	if(ans!=9999999)
		m[xx].l=ans;
}

inline void findr(int xx)
{
	int ll=xx,rr=n,mid,ans=-1;
	while(ll<=rr)
	{
		mid=(ll+rr)>>1;
		if(x[mid]>x[xx]+r[xx])
			rr=mid-1;
		else{ll=mid+1;ans=max(ans,m[mid].r);m[xx].l=min(m[xx].l,m[mid].l);}
		}	
	if(ans!=-1)
		m[xx].r=ans;
}

int main()
{
	long long ans=0;
	for(int i=2;i<=n;i++)
		findl(i);
	for(int i=n-1;i>=1;i--)
		findr(i);
	for(int i=1;i<=n;i++)
		ans=(ans+(m[i].r-m[i].l+1)*(long long)i)%1000000007;
}