Cho dãy số gồm N phần tử A1, A2, ..., AN (1 <= n <= 10⁵). Hãy tìm một đoạn con liên tiếp các phần tử có tổng lớn nhất.

Input:

• Dòng đầu tiên nhập số N
• Dòng tiếp theo nhập các số A₁, A₂, …, A_N;  ^|A_i| <=10⁶

Output:

• Một số duy nhất là tổng lớn nhất của các giá trị các phần tử liên tiếp nhau

Ví dụ