ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Championship 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Tears of Drowned

Time limit: 1.0 second
Memory limit: 64 MB
Tia Dalma: Come. What service may I do you? You know I demand payment.
Jack: I brought payment. Look. An undead monkey. Top that.
Tia Dalma: The payment is fair.
Old Captain Jack Sparrow’s friend Tia Dalma, the fortuneteller and prophetess, often makes potions. She has an outstanding collection of the rarest ingredients such as rat tails, fingers of drowned, tears of virgins and so on. And all these ingredients require special care.
Recently Tia Dalma received some good skins of bats as a payment, and now she wants to dry them. To dry ingredients fortuneteller usually uses specially prepared books as the magical properties of the skins could be lost during prolonged contact with other objects. Tia Dalma knows how many sheets should be on both sides of the skin to save it unspoiled. For a i-th skin that number is ai, that is, the distance from it to the neighboring skins and the book cover can’t be less than ai sheets. Help a fortuneteller determine the minimum number of sheets that should be in the book to save rare ingredients from damage.

Input

The first line contains integer n  that is the number of skins (1 ≤ n ≤ 100). The second line contains n integers ai (1 ≤ ai ≤ 100).

Output

Output the minimal required number of sheets in the book.

Sample

inputoutput
3
5 10 3
28
Problem Author: Tatiana Sharypova (prepared by Oleg Dolgorukov)
Problem Source: Open Ural FU Championship 2012
To submit the solution for this problem go to the Problem set: 1935. Tears of Drowned