Description

有 $n$ 个人围成一圈在打牌，其座位按逆时针顺序依次为 1 号、2 号直到 $n$ 号（也就是说，对于 $i\ (i<n)$ 号其右手边是 $i+1$ 号，$n$ 号的右手边为 $1$ 号）。规则很简单：轮次按照逆时针方向进行，轮到 $i$ 号时，若上一张牌是 $i$ 号打出的，则 $i$ 号必须打出一张牌，否则 $i$ 号可以选择过牌。当某个人率先打完其手中所有牌时，这个人就成为了赢家。

相信你也能看出，这是个很蠢的游戏。不过这 $n$ 个人也并不在乎谁会赢，他们只是找个借口凑在一起摆龙门阵罢了。一旦他们中有某个人赢下了这局游戏，他们的上司就要催促他们回工位干活了。所以他们想要这局游戏进行的越久越好。

现在 $i$ 号手中还剩下 $a_i$ 张牌，轮到 $1$ 号且上一张牌也是 $1$ 号打出的。若将打牌和过牌都看作一次操作，请问这场游戏最多还能进行多少次操作？

Input

第一行一个整数 $n$ ($1\le n \le 10^5$) 。

接下来 $n$ 个整数，第 $i$ 个整数表示 $a_i$ ($1\le a_i \le 10^5$)，表示第 $i$ 个人手中目前还剩下 $a_i$ 张牌。

Output

输出一个整数表示答案。

Samples

2
2 1

3

3
2 2 3

11

Note

第一个样例中，第一次 $1$ 号必须出牌，接着 $2$ 号过牌，最后 $1$ 号出最后一张牌，最多可以进行 $3$ 次操作。

请注意：答案可能会超出 32 位有符号整型数所能表示的范围。

Resources

电子科技大学第十五届 ACM 趣味程序设计竞赛