Sequence

时间限制:30s      空间限制:256MB

题目描述

给定一个序列AA为一个环,顺时针标号为1…n。定义dist(i,j)=(j-i+n)%n,表示从点i到点j顺时针方向的距离。点i能一步走到点j(i≠j)当且仅当,dist(i,j)<=Aj。求从每个点i出发走回点i的最小步数之和。


输入格式

      第一行一个正整数n。接下来n,每行一个整数Ai


输出格式

 
输出一行,一个数,为从每个点i出发走回点i的最小步数之和。


样例输入

3
2 
1 
1

样例输出

5


提示

对于100%的数据,2<=n<=250000,1<=Ai<=250000.


题目来源

倍增