← 返回题目列表

Codeforces · 201/C

C. 脆弱的桥梁

中文机器翻译题面 查看原题

您正在玩电子游戏,并且刚刚达到奖励级别,唯一可能的目标是获得尽可能多的分数。作为一名完美主义者,您决定在获得尽可能多的分数之前不会离开此级别。

奖励关卡由 n 个排成一排的小平台组成,从左到右编号为 1 到 n,以及连接相邻平台的 (n - 1) 座桥梁。平台之间的桥梁非常脆弱,对于每座桥梁来说,在它永远倒塌之前,人们可以通过这座桥从一端到达另一端的次数是预先知道的。

玩家的行动如下。首先,他选择一个平台作为他的英雄的起始位置。之后,玩家可以自由地移动英雄穿过未毁坏的桥梁移动的平台。一旦英雄发现自己处于一个没有未损坏的桥梁的平台上,关卡就会自动结束。玩家在关卡结束时获得的分数是根据英雄在平台之间进行的转换次数来计算的。请注意,如果英雄开始通过某座桥移动,他必须继续朝同一方向移动,直到到达平台上。

找出你需要得分多少分才能确保没有人会打破你的记录,然后安静地进入下一个级别。

输入

第一行包含一个整数 n (2 ≤ n ≤ 105) — 奖金级别的平台数量。第二行包含 (n - 1) 个整数 ai (1 ≤ ai ≤ 109, 1 ≤ i < n) — 平台 i 和 i + 1 之间的桥梁可以承受的从一端到另一端的转换次数。

输出

打印一个整数 - 玩家在奖金级别上可以获得的最大分数。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

5
2 1 2 1

输出 #1

5

注意

样本中获得 5 分的一种可能性是从平台 3 开始,然后移动到平台 4、3、2、1 和 2。之后唯一未损坏的桥梁是平台 4 和 5 之间的桥梁,但这座桥距离英雄现在所在的平台 2 太远。