Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
В магическом саду Звездных Цветов на планете Альфа-Карелия
выращивают удивительные растения. Они растут на круглой грядке,
и у каждого куста ровно два соседа. Всего на грядке растет N кустов.
Эти удивительные Звездные Цветы обладают различной магической силой,
определяемой числом звезд, которыми они излучают. Измеряют магию в звёздах. По мере приближения
времени сбора на Звездных Цветах вырастает разное количество звезд –
на i-ом кусте выросло ai звезд.
В магическом саду установлена система автоматического сбора магии. Эта система состоит из управляющего модуля и нескольких сборочных модулей. Сборочный модуль за один заход, находясь непосредственно перед некоторым кустом, собирает магию с этого куста и с двух соседних с ним.
Напишите программу для определения максимального количества магии, которое может собрать за один заход сборочный модуль, находясь перед некоторым кустом на заданной во входном файле грядке.
Входные данные:
Первая строка содержит целое число N (3 ≤ N ≤ 1000) –
количество кустов Звездных Цветов. Вторая строка содержит N целых
положительных чисел a1, a2, ..., aN
– количество звезд, выросшее на соответствующем кусте. Все ai не превосходят 1000.
Выходные данные:
Одно число - максимальное количество магии, которое может собрать за один заход сборочный модуль.
Для отправки решений необходимо выполнить вход.
|