Задача C. Транспортное кольцо ≡

Условие

Основная транспортная артерия города — дорога, имеющая форму кольца. Длина дороги составляет $N$ километров. На ней есть $N$ Т-образных перекрестков через каждый километр пути. Перекрестки пронумерованы числами от $1$ до $N$ в порядке обхода. Для каждого $i$ от $1$ до $N$, на $i$-ом перекрестке к кольцу примыкает дорога, имеющая длину $a_i$ километров.

Дорожная ситуация в городе критическая, поэтому было решено построить объездную дорогу, соединяющую две наиболее удалённые точки города. Под наиболее удаленными подразумеваются такие точки, что длина минимального пути, соединяющего их и проходящего только по имеющимся дорогам, максимальна. Ваша задача — найти расстояние между двумя наиболее удаленными точками.

Формат входного файла

Формат выходного файла

Выведите в выходной файл единственно число — искомое расстояние.

Ограничения

$3 \le N \le 2 \times 10^5$

$1 \le a_i \le 10^9$

Примеры тестов

6
1 1 3 1 4 4

10