섬

바이트랜드(Byteland)라는 섬에서는 모든 마을이 해안을 따라 원형으로 늘어서 있다. 해안을 따라 하나의 양방향 순환 도로가 모든 마을을 순서대로 잇고 있어서, 어떤 마을에서 출발하더라도 시계 방향이나 반시계 방향으로 순환 도로를 돌아 다른 모든 마을에 갈 수 있다. 두 마을 사이의 거리는 이 두 경로 중 더 짧은 쪽의 길이로 정의한다.

서로 라이벌인 두 축구팀의 팬들은 가능한 한 멀리 떨어진 두 마을에서 경기를 보고 싶어 한다. 섬에서 두 마을이 떨어질 수 있는 가장 큰 거리를 구하여라.

다음을 수행하는 프로그램을 작성하시오.

• 표준 입력에서 섬에 대한 정보를 읽는다,
• 임의의 두 마을 사이의 가능한 최대 거리를 계산한다,
• 그 거리를 표준 출력에 쓴다.

첫째 줄에 마을의 수를 나타내는 정수 $n$ ($2 \le n \le 50000$)이 주어진다. 마을은 순환 도로를 따라 순서대로 $1$번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $n$개의 줄에는 각각 순환 도로 한 구간의 길이를 나타내는 양의 정수가 하나씩 주어진다. $1 \le i \le n-1$인 경우, $i+1$번째 줄에는 마을 $i$과(와) 마을 $i+1$을(를) 잇는 도로의 길이가 주어진다. $n+1$번째 줄에는 마을 $n$과(와) 마을 $1$을(를) 잇는 도로의 길이가 주어진다.

순환 도로 전체의 길이는 $10^9$을 넘지 않는다.

두 마을이 떨어질 수 있는 최대 거리를 정수 하나로 출력한다.