print1448. Транспортное кольцо

printТранспортное кольцо

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11848.png
Основная транспортная артерия города – дорога, имеющая форму кольца. Длина дороги составляет `N` километров. На ней есть `N` Т-образных перекрестков через каждый километр пути. Перекрестки пронумерованы числами от 1 до `N` в порядке обхода. Для каждого `i` от 1 до `N`, на `i`-ом перекрестке к кольцу примыкает дорога, имеющая длину `a_i` километров.
Дорожная ситуация в городе критическая, поэтому было решено построить объездную дорогу, соединяющую две наиболее удалённые точки города. Под наиболее удаленными подразумеваются такие точки, что длина минимального пути, соединяющего их и проходящего только по имеющимся дорогам, максимальна. Ваша задача – найти расстояние между двумя наиболее удаленными точками.
Формат входного файла
В первой строке входного файла содержится число `N`. Во второй строке содержатся целые числа `a_i`.
Формат выходного файла
Выведите в выходной файл единственно число – искомое расстояние.
Ограничения
`3\ ≤\ N\ ≤\ 2*10^5`, `1\ ≤\ a_i\ ≤\ 10^9`

Пример ввода

6
1 1 3 1 4 4

Пример вывода

10
Источник: Отборочные соревнования ВКОШП Дальневосточного региона, 2008
loading