Cho một mảng số nguyên, hãy tính tổng lớn nhất một mảng con không trống (các phần tử liền kề) có tối đa một phần tử bị xóa. Nói cách khác, chọn một mảng con và tùy ý xóa một phần tử khỏi nó để vẫn còn ít nhất một phần tử và tổng các phần tử còn lại là lớn nhất có thể.

Lưu ý rằng mảng con cần phải không trống sau khi xóa một phần tử.

Ràng buộc:

• \(1 <= arr.length <= 105\)
• \(-10^4 <= arr[i] <= 10^4\)

Example

Sample input 1

4
1 -2 0 3

Sample output 1

4

Giải thích 1

Chọn mảng con [1, -2, 0, 3] vào xóa -2. Sẽ được tổng 4.

Sample input 2

4
1 -2 -2 3

Sample output 2

3

Giải thích 2

Chỉ chọn 1 số 3.

Sample input 3

4
-1 -1 -1 -1

Sample output 3

-1

Giải thích 3

Mảng phải có ít nhất 1 phần tử nên chỉ có 1 cách là -1