Կարելիայի ագրարային տնտեսություններից մեկում աճեցնում են մոշ: Այն աճում է կլոր հողամասի վրա, ընդ որում թփերը աճեցրած են միայն շրջանագծով: Այս կերպ ամեն թուփ ունի երկու հարևան թուփ: Հողամասում ընդհանուր առմամբ աճում է n թուփ:

  Այդ թփերն ունեն տարբեր բերքատվություն, այդ պատճառով հավաքելու ժամանակ դրանց վրա աճել են տարբեր քանակությամբ հատապտուղներ i-երորդ թփի վրա աճել է a_i հատապտուղ:

  Այդ ագրարային տնտեսությունում ներմուծված է մոշի հավաքման ավտոմատացված համակարգ: Այդ համակարգը բաղկացած է HARVEST անունով ռոբոտից, որը ղեկավարում է մի քանի հավաքող մոդուլների աշխատանքը: Յուրաքանչյուր հավաքող մոդուլը, գտնվելով որևիցե թփի առաջ, միանգամից հավաքում է այդ և հարևան երկու թփերի մոշերը:

  Ձեզնից պահանջվում է գրել ծրագիր, որը կգտնի մոշի առավելագույն քանակությունը, որը կարող է հավաքել հավաքող մոդուլը միանգամից գտնվելով որևէ թփի դիմաց:

Մուտքային տվյալներ

  Մուտքի առաջին տողը պարունակում է թփերի քանակը մեկ ամբողջ թիվ n (3≤n≤1000) : Երկրորդ տողը պարունակում է  ամբողջ դրական թվեր a₁, a₂, ..., a_n համապատասխան թփի վրա աճող մոշի քանակությունը, a_i-երը չեն գերազանցում 1000-ը:

Ելքային տվյալներ

  Պետք է արտածել խնդրի պատասխանը:

Օրինակներ