friends

Адизор разбрал, че някои от проблемите му се дължат на неправилния избор на приятели. Затова той взел важно решение: ще остане приятел само с някои от старите си приятели.
Ето какво направил. Отначало номерирал всичките
n приятели с числата от 1 до n. След това на приятеля с номер i дал целочислена оценка Ci, наречена "качество", което  представлява алгебрична сума от положителните и отрицателните качества на съответния човек. После разположил оценките в кръг една след друга C1, C2,…Cn, така че Cn се оказала съседна на C1.
Накрая той измислил критерий, по който ще избира дали някой ще остане негов приятел от днес нататък. Целта му е да постигне максимална стойност
S, посредством сумиране на индивидуалните оценки на избраните приятели. Разполагането на хората около кръга не е случайно: Адизор е поставил един до друг хората с подобно поведение, затова той не трябва да избира двама души, чиито оценки са разположени на съседни позиции около кръга.
Помогнете на Адизор да избере своите бъдещи приятели, така че да бъдат спазени изброените ограничения.

Задача

Напишете програма, която определя максималната възможна сума S, на някои от числата C1, C2,…Cn, при ограничението никои две съседни числа да не участват едновременно в сумата. Съседни са Ci-1 и  Ci за i=2,3,…,n, а също така Cn и C1.

Вход

Файлът friends.in съдържа на първия ред цяло положително число n, представляващо броя на приятелите на Адизор. Започвайки от втория ред във файла са записани n цели числа C1, C2, … Cn, по едно на ред, представляващи оценките за всеки човек.

Изход

Файлът friends.out трябва да съдържа един ред, на който е записано положително цяло число S, със смисъл, обяснен по-горе.

Ограничения

 

Пример

friends.in

friends.out

Обяснение

5
7
3
-2
1
6

9

Адизор избира приятелите с оценки 3 и 6.

 

Време за работа на програмата:  0.1 секунди на тест

 

prof. Constantin Galatan
C.N. "Liviu Rebreanu" Bistriţa
tucu_galatan@yahoo.com

Превод на български: Стоян Капралов