金环线是贝尔兰的特色旅游线路。这条路线由 $$$n$$$ 城市和循环铁路线组成。城市编号从 $$$1$$$ 到 $$$n$$$,以便:
- $$$1$$$ 的下一个城市是 $$$2$$$ 城市,
- $$$2$$$ 的下一个城市是 $$$3$$$ 城市,
- ...
- $$$n$$$ 的下一个城市是城市 $$$1$$$。
因此,路线是一个循环,城市按行进方向编号(路线以单向定向)。
博主 Polycarp 想要在 $$$1$$$ 城市开始他的旅程。对于每个城市,他都知道 $$$a_i$$$ 的价值——他想在第 $$$i$$$ 个城市拍多少张自拍照。他每次访问每个城市最多只能拍一张自拍照。由于他乘火车旅行,因此他无法跳过城市(他总是从城市 $$$i$$$ 移动到城市 $$$i+1$$$,$$$1 \le i < n$$$ 并从 $$$n$$$ 移动到 $$$1$$$)。因此,当火车停在城市时,波利卡普必须访问这座城市。如果坡旅甲多次访问该城市,则所有访问均单独计算。
波利卡普至少需要完成多少次城市访问才能实现他对每个城市的自拍照数量的计划?请注意,他总是访问城市 $$$1$$$,因为他的旅程就是从这个城市开始的。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2\cdot10^5$$$) — Berland 金环中的城市数量。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 等于第 $$$i$$$ 个城市所需的自拍照数量。
保证 $$$a_i$$$ 中至少有一个数字严格大于零。
输出
打印一个整数——所需的最小访问次数。
示例
输入 #1
3 1 0 0
输出 #1
1
输入 #2
3 2 0 2
输出 #2
6
输入 #3
5 0 3 1 3 2
输出 #3
14
输入#4
5 1000000000 1000000000 1000000000 1000000000 0
输出#4
4999999999