무한 수열

세훈이는 생일 기념으로 $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페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.