题目描述

给定一个序列$A$。$A$为一个环，顺时针标号为$1\ldots n$。定义$dist(i,j)=(j-i+n)\%n$,表示从点$i$到点$j$顺时针方向的距离。

点$i$能一步走到点$j(i≠j)$当且仅当，$dist(i,j)\le A_j$。求从每个点$i$出发走回点$i$的最小步数之和。

输入格式

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

输出格式

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

样例

3
2
1
1

5

数据规模与约定

对于$100\%$的数据：$2\le n\le 250000,1\le A_i\le 250000$.