7265번 - Herbamedžiai 서브태스크다국어

Ūkininkė Ugnė savo sode pasodino N herbamedžių. Ji juos pasodino tiesia linija ir sunumeravo iš eilės nuo 1 iki N.

Deja, vos tik pasirodė pirmosios uogų užuomazgos, Ugnė suprato, kad medžiai yra susodinti per tankiai. Jei ji nieko nesigriebs, greta augantys medžiai užgoš vieni kitus ir ji šiais metais liks be herbauogių.

Norėdama to išvengti, Ugnė planuoja persodinti kai kuriuos medžius – šie medžiai derliaus nebeduos. Jei Ugnė nori palikti medį i, jai būtinai teks persodinti medžius i − 1 ir i + 1.

Kaip Ugnei pasirinkti medžius persodinimui, kad likęs derlius būtų kiek įmanoma didesnis?

Pirmoje eilutėje pateikiamas medžių skaičių N. Likusiose N eilučių pateikiama po skaičių A_i – užsimezgusių uogų kiekį i-tajame medyje.

Jums reikia išvesti vieną skaičių – kiek daugiausiai uogų gali tikėtis Ugnė, jei medžius ji persodins optimaliai.

• 1 ≤ N ≤ 100 000
• 1 ≤ A_i ≤ 1 000