Trên một vòng tròn người ta đánh dấu $N$ vị trí. Các vị trí được dánh số thứ tự từ $1$ đến $N$ theo chiều kim đồng hồ. Tại vị trí $i$ người ta ghi số nguyên $a_i$ ($i=1,2,...,n$).

Yêu cầu

Tìm các chọn ra dãy con gồm các số liên tiếp trên vòng tròn (cùng chiều kim đồng hồ) có tổng các số hạng là lớn nhất.

Input

Vào từ file văn bản CAU3.INP:

• Dòng đầu tiên ghi số nguyên dương $N$ ($N\le {10}^6$)
• Dòng thứ $i$ trong số $N$ dòng tiếp theo ghi số $a_i$ ($|a_i|\le 32000,i=1,2,...,n$)

Output

Ghi ra file văn bản CAU3.OUT một số duy nhất là tổng lớn nhất của các số trong dãy con

Sample Input

11
-10
-1
-3
5
6
-4
-9
20
-5
7
-3

Sample Output

22