Задача C. Транспортное кольцо ≡
| Автор: | И. Туфанов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
Условие
Основная транспортная артерия города — дорога, имеющая форму кольца.
Длина дороги составляет N километров. На ней есть N Т-образных перекрестков
через каждый километр пути.
Перекрестки пронумерованы числами от 1 до N в порядке обхода.
Для каждого i от 1 до N, на i-ом перекрестке к кольцу
примыкает дорога, имеющая длину ai километров.
Дорожная ситуация в городе критическая, поэтому было решено построить объездную дорогу, соединяющую две наиболее удалённые точки города. Под наиболее удаленными подразумеваются такие точки, что длина минимального пути, соединяющего их и проходящего только по имеющимся дорогам, максимальна. Ваша задача — найти расстояние между двумя наиболее удаленными точками.
Формат входного файла
В первой строке входного файла содержится число N. Во второй строке содержатся целые числа ai.Формат выходного файла
Выведите в выходной файл единственно число — искомое расстояние.
Ограничения
3 ≤ N ≤ 2 × 105
1 ≤ ai ≤ 109
Примеры тестов
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|