Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Fragile Bridges

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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* < *n*) — the number of transitions from one end to the other that the bridge between platforms *i* and *i* + 1 can bear.

Output

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.

Examples

Input

5

2 1 2 1

Output

5

Note

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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/21/2020 01:55:14 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|