Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача D. Типичная ситуация

Задачу добавил: alef

Успешно сдано решений: 356

Ограничение по времени на тест:2 секунды
Ограничение по памяти на тест:256 мегабайт

Поинтересовался Калистрат у Силантия — может, спортивно-туристический комплекс, по его мнению, и вовсе строить не надо? И в соревнованиях по водному поло не участвовать?

Силантий на то отвечал, что ежели о соревнованиях речь, так надо не один большой комплекс строить, а много бассейнов. Секции водного поло при них открыть. А там и команды появятся, игроки хорошие. Будет из кого сборную сформировать. К тому же, если в каждом районе царства по бассейну построить, это в сумме дешевле большого комплекса выйдет.

Царство можно представить как последовательно расположенные n районов. При этом район #i соседствует слева с районом #(i - 1), а справа — с районом #(i + 1) (исключением являются районы #1 и #n, у них по одному соседнему району).

Силантий предлагает построить в каждом районе по одному бассейну, а чтобы строительство обошлось дешевле, строить все бассейны по одному типовому проекту, рассчитанному на некоторое количество жителей b.

В районе #i проживает ai жителей. Жители района #i захотят посещать бассейн либо в своём районе, либо в одном из соседних — #(i - 1) или #(i + 1).

Заметим, что жители не оказывают предпочтения бассейну в собственном районе; может даже сложиться такая ситуация, что (при возможности) жители района #i ходят в бассейны районов #(i - 1) и #(i + 1), в то время как жители районов #(i - 1) и #(i + 1) посещают бассейн района #i. Важно то, что если бассейн рассчитан на b жителей, большее количество жителей записаться в него не смогут.

Ваша задача — выяснить, на какое минимально возможное количество жителей b должен быть рассчитан типовой проект бассейна, чтобы все жители могли посещать бассейн в своём или соседних районах.

Входные данные

В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество районов в царстве.

Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 105,  i = 1, 2, ..., n), где ai — количество жителей, проживающих в районе #i.

Выходные данные

Выведите единственное целое число b — минимально возможное количество жителей, на которое должен быть рассчитан типовой проект бассейна.

Система оценки

Подзадача 1 (30 баллов)

n ≤ 100,  ai ≤ 1000.

Баллы начисляются, если пройдены все тесты в группе.

Подзадача 2 (70 баллов)

n ≤ 105,  ai ≤ 105.

Баллы начисляются, если пройдены все тесты в группе.

По запросу выводится результат проверки на каждом тесте.

Пример

Входные данные
6
5 13 3 10 4 8
Выходные данные
8
Примечание

Поясним пример входных и выходных данных.

Если бассейн будет рассчитан на 8 жителей, то распределение жителей по бассейнам может быть, например, таким.

Все жители района #1 посещают бассейн в своём районе.

Жители района #2 посещают бассейны в своём и соседних районах: двое в районе #1, семеро в своём районе, четверо — в районе #3.

Все жители района #3 посещают бассейн в своём районе.

Семеро жителей района #4 посещают бассейн в своём районе, а трое — в районе #5.

Все жители района #5 посещают бассейн в своём районе.

Все жители района #6 посещают бассейн в своём районе.

Как можно видеть, во все бассейны, кроме бассейна в районе #6, будет ходить по 7 жителей, а в бассейн в районе #6 будет ходить 8 жителей.

Сдать задачу

Задать вопрос жюри по этой задаче