두 개의 탑
시간 제한2초메모리 제한128 MB
원형으로 연결된 N개 점의 구간 거리가 주어질 때, 두 지점 사이의 최단 경로 거리가 최대가 되도록 두 지점을 선택합니다.
문제
1번부터 N번까지 N개의 지점이 원형으로 순서대로 연결되어 있다. 인접한 두 지점 사이의 거리가 각각 주어진다. 이 지점 중 서로 다른 두 곳에 탑을 하나씩 세울 때, 두 탑 사이의 거리를 최대한 크게 만들려고 한다.
두 지점 사이에는 시계 방향과 반시계 방향의 두 경로가 있다. 두 탑 사이의 거리는 두 경로 길이 중 더 짧은 값으로 정의한다.
두 탑 사이 거리의 최댓값을 구하라.
입력
첫째 줄에 지점의 개수 N(2 <= N <= 50,000)이 주어진다.
다음 N개의 줄에는 1번과 2번, 2번과 3번, ..., N번과 1번을 잇는 인접 구간의 거리가 순서대로 주어진다. 각 거리는 양의 정수이며, 모든 거리의 합은 1,000,000,000 이하이다.
출력
두 탑 사이 거리의 최댓값을 출력한다.