28355번 - 무한 수열

문제

세훈이는 생일 기념으로 $ N $개의 정수로 이루어진 수열 $ A $를 선물로 받았다. 하지만 수열의 길이가 너무 짧다고 생각한 세훈이는 다음과 같은 방식으로 무한히 긴 수열을 만들기로 했다.

우선 수열 $ A $를 무한히 이어 붙인 뒤, 모든 양의 정수 $ i $에 대해 $ i $번째 수에서 $ i $를 뺀다.

수열의 길이가 길어졌음에 만족한 세훈이는 이렇게 만들어진 수열에서 연속된 몇 개의 수를 선택해서 더해보기로 했다. 물론 큰 것을 좋아하는 세훈이는 이러한 합을 최대로 만들고 싶어졌다.

예를 들면, 수열 $ A $가 $ [9, 1, 7] $이었다면, 새로 만들어진 수열은 $ [8, -1, 4, 5, -4, 1, \ldots] $가 되고, 이 수열의 최대 연속합은 $ 1 $번째 수부터 $ 4 $번째 수까지의 합인 $ 8-1+4+5 = 16 $이 된다.

입력

첫째 줄에는 수열 $ A $의 길이 $ N $이 주어진다. $( 1 \le N \le 500,000円 )$

둘째 줄에는 수열 $ A $의 원소 $ A_1, A_2, \ldots, A_N $이 공백으로 구분되어 주어진다. $( |A_i| < 2^{31} )$

출력

문제의 정답을 출력한다.

제한

노트

입출력 양이 많으므로 문제지 2-4페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.