두 개의 탑

1번부터 N번까지 N개의 지점이 원형으로 순서대로 연결되어 있다. 인접한 두 지점 사이의 거리가 각각 주어진다. 이 지점 중 서로 다른 두 곳에 탑을 하나씩 세울 때, 두 탑 사이의 거리를 최대한 크게 만들려고 한다.

두 지점 사이에는 시계 방향과 반시계 방향의 두 경로가 있다. 두 탑 사이의 거리는 두 경로 길이 중 더 짧은 값으로 정의한다.

두 탑 사이 거리의 최댓값을 구하라.

첫째 줄에 지점의 개수 N(2 <= N <= 50,000)이 주어진다.

다음 N개의 줄에는 1번과 2번, 2번과 3번, ..., N번과 1번을 잇는 인접 구간의 거리가 순서대로 주어진다. 각 거리는 양의 정수이며, 모든 거리의 합은 1,000,000,000 이하이다.

두 탑 사이 거리의 최댓값을 출력한다.