题目描述

你正在玩一款电子游戏，刚打到奖励关，这一关唯一的目标就是尽可能多得分。作为完美主义者，你决定不拿到这一关的最高分就不离开。

奖励关由 $n$ 个排成一行的小平台组成，从左到右编号为 1 到 $n$，相邻平台之间由 $n-1$ 座桥连接。这些桥都非常脆弱：每座桥"从一端走到另一端"的可用次数是预先知道的，用完就会永久坍塌。

玩家的行动如下：首先选一个平台作为主角的起点。然后玩家可以让主角随意在平台间移动，走过的桥必须还未坍塌。一旦主角发现自己位于一个没有任何未坍塌的桥相连的平台上，关卡自动结束。玩家最终得分等于主角在平台间移动的次数。注意：主角一旦开始过某座桥，就必须沿同一方向继续移动，直到到达一个平台为止。

求要拿到多高的分数，才能确保没人能打破你的记录，然后安心进入下一关。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示奖励关的平台数。第二行包含 $n-1$ 个整数 $a_i$（$1 \le a_i \le 10^9$，$1 \le i \lt n$），表示平台 $i$ 与平台 $i+1$ 之间的桥能承受的单向通过次数。

输出格式

输出一个整数——玩家在奖励关能拿到的最高分。

5
2 1 2 1

5

说明/提示

样例中拿 5 分的一种走法是：从平台 3 出发，依次移动到平台 4、3、2、1、2。之后唯一未坍塌的桥是平台 4 和 5 之间的那座，但它离主角所在的平台 2 太远了。