Fragile Bridges

题意翻译

您正在玩一个电子游戏，您的目标是获得尽可能多的分数。 这个游戏包含 $n$ 个平台，从左到右编号为 $1 \sim n$，相邻的两个平台间有一座桥。这些桥十分脆弱，游戏中会给出每座桥最多能走过的次数，第 $i$ 座桥的次数为 $a_i$。如果走这座桥走了 $a_i$ 次后这座桥就回断裂，再也不能走了。 游戏的过程是这样的： - 首先找到一个起始的平台； - 如果两边有桥，可以选择一边行走。如果走过一座桥之后走过的次数已经超过了 $a_i$，这座桥就会断裂； - 如果当前所在的平台已经没有桥连接到另外任意一个平台，游戏结束。 在游戏结束时会计算分数。分数即为走过桥的次数。 请问最大的分数是多少？

题目描述

You are playing a video game and you have just reached the bonus level, where the only possible goal is to score as many points as possible. Being a perfectionist, you've decided that you won't leave this level until you've gained the maximum possible number of points there. The bonus level consists of $ n $ small platforms placed in a line and numbered from $ 1 $ to $ n $ from left to right and ( $ n-1 $ ) bridges connecting adjacent platforms. The bridges between the platforms are very fragile, and for each bridge the number of times one can pass this bridge from one of its ends to the other before it collapses forever is known in advance. The player's actions are as follows. First, he selects one of the platforms to be the starting position for his hero. After that the player can freely move the hero across the platforms moving by the undestroyed bridges. As soon as the hero finds himself on a platform with no undestroyed bridge attached to it, the level is automatically ended. The number of points scored by the player at the end of the level is calculated as the number of transitions made by the hero between the platforms. Note that if the hero started moving by a certain bridge, he has to continue moving in the same direction until he is on a platform. Find how many points you need to score to be sure that nobody will beat your record, and move to the next level with a quiet heart.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2<=n<=10^{5} $ ) — the number of platforms on the bonus level. The second line contains ( $ n-1 $ ) integers $ a_{i} $ ( $ 1<=a_{i}<=10^{9} $ , $ 1<=i&lt;n $ ) — the number of transitions from one end to the other that the bridge between platforms $ i $ and $ i+1 $ can bear.

输出格式

Print a single integer — the maximum number of points a player can get on the bonus level. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

5
2 1 2 1

输出样例 #1

5

说明

One possibility of getting $ 5 $ points in the sample is starting from platform $ 3 $ and consequently moving to platforms $ 4 $ , $ 3 $ , $ 2 $ , $ 1 $ and $ 2 $ . After that the only undestroyed bridge is the bridge between platforms $ 4 $ and $ 5 $ , but this bridge is too far from platform $ 2 $ where the hero is located now.