Cho dãy 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.

Input

Vào từ file văn bản SUBSEQ.INP có cấu trúc:

• Dòng đầu tiên ghi số nguyên dương ~n~ với ~n \leq 10^6~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ ghi số nguyên ~a_i~ với ~|a_i| \leq 10^8~.

Output

Ghi ra file văn bản SUBSEQ.OUT theo quy định:

• 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í của phần tử 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.
• Nếu có nhiều tổng lớn nhất bằng nhau, ưu tiên đoạn con ngắn nhất và ở trước.

Example input 1

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

Example output 1

3
6
40