~Cho một dãy số nguyên gồm N phần tử a1,a2,…,a_N. Yêu cầu: Tìm hai dãy con liên tiếp không giao nhau sao cho tổng của các phần tử trong cả hai dãy là lớn nhất (mỗi dãy con chứa ít nhất một phần tử).

Input:

Dòng đầu gồm duy nhất một số nguyên dương N (N≤〖10〗^5 );
Dòng thứ hai gồm N số nguyên a_1,a_2,…,a_N  (|a_i |≤〖10〗^9 ).

Output: In ra kết quả bài toán.

Ví dụ:

DP_B2.INP               DP_B2.OUT
7
8 -2 4 -2 9 1 -3            20