Задача D. Типичная ситуация
Задачу добавил: alef
Успешно сдано решений: 403
Поинтересовался Калистрат у Силантия — может, спортивно-туристический комплекс, по его мнению, и вовсе строить не надо? И в соревнованиях по водному поло не участвовать?
Силантий на то отвечал, что ежели о соревнованиях речь, так надо не один большой комплекс строить, а много бассейнов. Секции водного поло при них открыть. А там и команды появятся, игроки хорошие. Будет из кого сборную сформировать. К тому же, если в каждом районе царства по бассейну построить, это в сумме дешевле большого комплекса выйдет.
Царство можно представить как последовательно расположенные 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 жителей.