Cho mảng ~a~ gồm ~n~ phần tử. Hãy tìm hai đoạn con liên tiếp, không giao nhau, khác rỗng của mảng ~a~, sao cho tổng của hai đoạn con đó là lớn nhất.

Nói cách khác, hãy tìm ra bộ bốn chỉ số ~i, j, u, v~ (~1 \le i \le j < u \le v \le n~), sao cho tổng ~a[i...j] + a[u...v]~ là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~2 \le n \le 3 \times 10^5~) là số phần tử của mảng.

Dòng thứ hai gồm ~n~ số nguyên ~a_i~ (~0 \le |a_i| \le 10^9~) là các phần tử của mảng.

Output

Tổng lớn nhất của hai đoạn con không giao nhau, khác rỗng.

Sample Input 1

5
3 -2 5 -3 4

Sample Output 1

10

Notes

Để đạt tổng lớn nhất là ~10~, ta chọn đoạn con ~[1, 3]~ và đoạn con ~[5, 5]~. Đây là hai đoạn con có tổng dương lớn nhất, không giao nhau, nên kết quả ~6 + 4 = 10~ là tối ưu.