C. Хрупкие мосты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вы играете в компьютерную игру и только что дошли до бонусного уровня, единственная возможная цель которого — набрать как можно больше очков. Будучи максималистом, вы решили, что не уйдете с этого уровня, не набрав максимально возможное количество очков на нем.

Бонусный уровень состоит из 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.

Примеры
Входные данные
5
2 1 2 1
Выходные данные
5
Примечание

Один из вариантов получить 5 очков в примере — начав с платформы 3, последовательно переходить на платформы 4, 3, 2, 1 и 2. После этого единственным нерухнувшим мостом останется мост между платформами 4 и 5, однако этот мост слишком далек от платформы 2, на которой расположен герой.