Cho dãu gồm ~n~ số nguyên ~a_1,a_2,…,a_n~. Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương ~n~ ~(n≤10^6)~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo ghi số nguyên ~a_i~ ~(|a_i |≤10^8)~.

**Kết quả: **

• Dòng đầu ghi vị trí của phần tử đầu tiên của dãy tìm được.
• Dòng thứ hai ghi vị trí cuối cùng của dãy con tìm được.
• Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.

Dữ liệu luôn đảm bảo kết quả là duy nhất.

Ví dụ:

Input

8
12
-14
1
23
-6
22
-34
13 

Output

3
6
40