Cho một mảng số nguyên vòng \(a\) độ dài \(n\). Hãy tìm tổng lớn nhất có thể của một mảng con liên tiếp không rỗng của \(a\).

Mảng vòng có nghĩa là phần tử cuối của mảng nối liền với phần tử đầu tiên của mảng. Cụ thể hơn, phần tử ngay sau \(a_i\) là \(a_{(i + 1) \bmod n}\) và phần tử ngay trước \(a_i\) là \(a_{(i - 1 + n) \bmod n}\).

Lưu ý: Một mảng con chỉ được chứa mỗi phần tử của mảng ban đầu tối đa một lần. Nghĩa là với một mảng con \(a_i, a_{i+1}, \dots, a_j\), độ dài của mảng con này không được vượt quá \(n\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) — số lượng phần tử của mảng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) cách nhau bởi khoảng trắng.

Output

• In ra một số nguyên duy nhất là tổng lớn nhất của mảng con vòng.

Constraints

• \(1 \le n \le 3 \cdot 10^4\)
• \(-3 \cdot 10^4 \le a_i \le 3 \cdot 10^4\)

Example

4
1 -2 3 -2

3

3
5 -3 5

10

3
-3 -2 -3

-2

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \le n \le 5000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.