题目描述

您正在玩一个电子游戏，您的目标是获得尽可能多的分数。

这个游戏包含 $n$ 个平台，从左到右编号为 $1\sim n$，相邻的两个平台间有一座桥。这些桥十分脆弱，游戏中会给出每座桥最多能走过的次数，第 $i$ 座桥的次数为 $a_i$。如果走这座桥走了 $a_i$ 次后这座桥就回断裂，再也不能走了。

游戏的过程是这样的：

• 首先找到一个起始的平台；
• 如果两边有桥，可以选择一边行走。如果走过一座桥之后走过的次数已经超过了 $a_i$，这座桥就会断裂；
• 如果当前所在的平台已经没有桥连接到另外任意一个平台，游戏结束。

在游戏结束时会计算分数。分数即为走过桥的次数。请问最大的分数是多少？

输入格式

第一行一个整数 $n$，$2\le n\le 10^5$。

第二行 $n-1$ 个整数 $a_i$，$1\le a_i\le 10^9$。

输出格式

输出一个整数，表示答案。

5
2 1 2 1

5