Từ khi An cài được phần mềm học tiếng anh với mật khẩu tìm được từ dãy số mà nhà sản xuất đã tặng, An rất thích thú với dãy số đã cho. Một hôm, An đến nhà Lâm chơi và kể cho Lâm nghe về việc được tặng một dãy số mật khẩu, nhìn thấy dãy số An nảy sinh ý tưởng và rủ Lâm chơi trò chơi tìm số. Hai bạn lần lượt mỗi người viết một số nguyên lên giấy roki, An viết số thứ nhất, Lâm viết số thứ hai, rồi đến lượt An viết số thứ ba,… Cứ tiếp tục như vậy hai bạn viết được một dãy gồm n số a1, a2, …, an. Đến đây hai bạn chưa kịp chơi trò chơi của mình thì bố của Lâm đi làm về, Bố của Lâm cũng là một giáo viên dạy môn toán cấp 2. Ông tiến lại gần, sẵn thấy dãy số ghi trên giấy, ông đã đặt ra câu đố và sẵn sàng trao thưởng nếu ai tìm ra được đáp án đúng, câu đố như sau: Tìm một đoạn liên tiếp các số trong dãy số trên sao cho tổng giá trị các số trong đoạn đó là lớn nhất. Vì dãy số có quá nhiều số nên cả hai bạn nhìn hoa cả mắt mà vẫn chưa tìm ra được đáp án. Bạn hãy lập trình giải giúp hai bạn nhé.

Yêu cầu: Em được cho biết n và dãy a1, a2, …, an. Tìm dãy số liên tiếp có tổng lớn nhất trong dãy a₁, a₂, …, a_n.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên n (1≤ n ≤ 10⁶).

+ Dòng thứ hai ghi dãy n số nguyên a1, a2, …, an (-1000 ≤ ai ≤ 1000, i=1..n)

Kết quả: Ghi một số nguyên duy nhất là tổng lớn nhất của một đoạn liên tiếp các số trong dãy tìm được.

Ví dụ:

Ràng buộc:

+ Có 40% test ứng với 40% điểm của bài có 1≤ n ≤ 10²;

+ Có 30% test ứng với 30% điểm của bài có 10² < n ≤ 10³;

+ Có 30% test ứng với 30% điểm của bài có 10³ < n ≤ 10⁶;