무한 수열

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