Bốn Đoạn

Cho một mảng gồm $n$ số nguyên. Với hai chỉ số $l$ và $r$ thỏa $0\le l\le r\le n$, ký hiệu $\text{sum}(l,r)$ là tổng các phần tử ở vị trí từ $l$ đến $r-1$ (tính phần tử thứ $l$, không tính phần tử thứ $r$). Các vị trí trong mảng được đánh số từ $0$. Khi $l=r$ thì $\text{sum}(l,r)=0$.

Ví dụ, nếu $a=[-5,3,9,4]$ thì $\text{sum}(0,1)=-5$, $\text{sum}(0,2)=-2$, $\text{sum}(1,4)=16$.

Hãy chọn ba chỉ số phân cách $deli{m}_0,deli{m}_1,deli{m}_2$ thỏa $0\le deli{m}_0\le deli{m}_1\le deli{m}_2\le n$ sao cho giá trị

$$res=\text{sum}(0,deli{m}_0)-\text{sum}(deli{m}_0,deli{m}_1)+\text{sum}(deli{m}_1,deli{m}_2)-\text{sum}(deli{m}_2,n)$$

đạt giá trị lớn nhất. Lưu ý một số đoạn có thể rỗng (khi hai đầu mút bằng nhau).

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_0,a_1,\dots ,a_{n-1}$.

Dữ liệu ra

In ra ba chỉ số $deli{m}_0,deli{m}_1,deli{m}_2$ làm cho $res$ đạt giá trị lớn nhất. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le n\le 5000$
• $-{10}^9\le a_i\le {10}^9$

Ví dụ