408800: GYM103325 D Колонизаторы - 2

D. Колонизаторы - 2ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Недавно вышла новая версия легендарной настольной игры «Колонизаторы»! Вы со своими друзьями, конечно же, не упустите шанс поиграть в новую игру.

Одной из основных механик игры является событие «Грабёж». Пусть сейчас играет $$$n$$$ человек, пронумерованных слева направо числами от $$$1$$$ до $$$n$$$. У $$$i$$$-го игрока в руке находятся $$$a_i$$$ карт. В момент, когда происходит событие «Грабёж», происходит следущее:

1. Сначала все игроки одновременно выполняют действие: найти ближайшего игрока справа, у которого в руке больше карт, и отдать ему одну карту.
2. Затем все игроки одновременно выполняют действие: найти ближайшего игрока слева, у которого в руке больше карт, и отдать ему одну карту.

Если у некоторого игрока нет необходимого соседа слева или справа, либо у него в руке нет ни одной карты, действие для данного игрока пропускается.

Вы с друзьями уже начали игру, и вот, внезапно, одно неаккуратное действие привело к событию «Грабёж». Выясните, какое максимальное количество карт в руке окажется у какого-то игрока после этого грабежа.

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

В первой строке записано целое число $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — количество игроков.

Во второй строке через пробел записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — количество карт в руках игроков.

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

Выведите одно целое число — максимальное количество карт в руке после события «Грабёж».

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

$$$$$$\begin{array}{|c|c|c|c|} \hline \text { Номер подзадачи } & \text { Баллы } & \text { Дополнительные ограничения } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \\ \hline 1 & 42 & 1 \le n \le 100 & \text {}\\ \hline 2 & 58 & \text { Нет дополнительных ограничений } & \text {1}\\ \hline \end{array}$$$$$$

ПримерыВходные данные

5
1 3 2 2 3

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

6

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

1
1

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

1

Примечание

Рассмотрим первый пример.

Количество карт у игроков после первой фазы «Грабежа»: $$$0, 4, 1, 1, 5$$$.

Количество карт у игроков после второй фазы «Грабежа»: $$$0, 6, 0, 0, 5$$$.

Максимальное количество карт после «Грабежа» — $$$6$$$.

Во втором примере $$$n = 1$$$, поэтому единственный игрок никому не отдаст свои карты.

Тесты к этой задаче состоят из 2 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Тесты из условия не оцениваются.