BOJ 8014 Island

문제 링크:

문제 내용

$n$개의 정점을 갖는 원형의 그래프가 주어집니다. 1번 정점과 2번 정점, 2번 정점과 3번 정점, …, $n$번 정점과 1번 정점이 연결되어 있습니다.

각 간선의 거리가 주어질 때, 서로 가장 멀리 떨어져 있는 두 정점 간의 거리를 구하세요.

입력

첫 번째 줄에는 정점의 개수 $n$이 주어집니다. ($2 \le n \le 50\;000$)

두 번째 줄부터 $n$줄에 걸쳐서, 1번 정점과 2번 정점 사이의 거리 $a_1$, 2번 정점과 3번 정점 사이의 거리 $a_2$, …, $n$번 정점과 1번 정점 사이의 거리 $a_n$이 주어집니다. 모든 값은 정수입니다. ($1 \le a_i \le 10^9$, $\sum a_i \le 10^9$)

출력

문제의 정답을 출력합니다.

문제 풀이