E. Хэврэг гүүр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Чи видео тоглоом тоглож байгаа ба одоо бонус үе дээр ирсэн байгаа. Энэ үед аль болох их оноо цуглуулах ёстой. Чи энэ үед боломжит хамгийн их оноог авах ёстой.

Энэ үе дээр зүүнээс баруун тийш $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг жижиг тавцан байдаг ба ($n - 1$) ширхэг гүүр хөрш тавцангуудыг холбосон байна. Энэ гүүрнүүд их хэврэг ба гүүр бүрт түүн дээгүүр явж өнгөрч болох тоо өгөгдсөн байна.

Тоглогчийн хийх зүйлс дараах байдалтай. Эхлээд аль нэг тавцанг эхлэх газраа болгон сонгоно. Дараа нь тэрээр эвдрээгүй гүүрээр дуртай зүг рүүгээ явж болно. Хэрэв тоглогч $2$ талынх нь гүүр эвдэрчихсэн тавцан дээр очвол бонус үе дуусна. Энэ үед цуглуулсан нийт оноо нь тавцангуудыг дамжсан нийт тоогоор тооцогдно. Тоглогч гүүрээр гарч эхэлсэн бол гүүрэн дээрээс эргэж буцна гэж байхгүй, цаад тавцанд заавал хүрэх ёстой.

Өөр тоглогч чиний амжилтыг эвдэхээргүй их оноо цуглуулах сайхан шүү дээ, тиймээс хамгийн ихдээ хэдэн оноо цуглуулах боломжтойг олоорой.

Оролт

Эхний мөрөнд тавцангийн тоо болох $n$ ($2 ≤ n ≤ 10^{5}$) байна. Дараагийн мөрөнд ($n - 1$) ширхэг бүхэл тоо байх ба $i$ дэхь тоо $a_{i}$ ($1 ≤ a_{i} ≤ 10^{9}$, $1 ≤ i < n$) нь $i$ болон $i+1$-дэх тавцанг холбосон гүүрийг гатлаж болох тоо юм.

Гаралт

Авч чадах хамгийн их оноог хэвлэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
5
2 1 2 1
Гаралт
5

Тэмдэглэл

Эхний жишээнд тоглогч $3$ дахь тавцангаас эхлэх ба $4$, $3$, $2$, $1$ ба $2$ гэсэн дарааллаар дамжлага хийн 5 оноо цуглуулах юм. Энэ үед $4$ ба $5$-р тавцанг холбосон гүүр л нураагүй үлдэх юм.

Сэтгэгдлүүдийг ачааллаж байна...