Rào dài Farmer John gồm cột và thanh ngang. $N$ ($1 \le N \le 3000$) cột nhãn số $-1000$ tới $+1000$, có thể trùng. Nhai lại bò nghĩ trò: “tổng rào tốt nhất” được kem tráng miệng.

Tìm đoạn liên tiếp dài nhất trong các đoạn có trị tuyệt đối tổng nhỏ nhất. Giúp tìm tổng thắng.

Dữ liệu vào

• Dòng 1: số nguyên $N$.

• Dòng $2..N+1$: nhãn cột, dòng 2 cột 1 v.v.

Dữ liệu ra

Một dòng ba số:

• Mã cột đầu cộng,

• Mã cột cuối cộng,

• Trị tuyệt đối tổng. Cùng tổng tốt nhất và chiều dài lớn nhất thì chọn mã đầu nhỏ nhất.

Ví dụ

Dữ liệu vào 1

6
5
10
-5
-6
2
4

Dữ liệu ra 1

4 6 0

Tác giả: Dominic Battre, 2001