Trong khi mọi người đang cùng nhau chuẩn bị quà sinh nhật cho ~Tesdizz~, mèo ~Capoo~ đã lén lút chuẩn bị thêm một món quà bất ngờ để chúc mừng cậu bạn thân của mình.

Cụ thể, với mảng ~a~ gồm ~n~ phần tử được đánh số ~1, 2, ..., n~ mà mọi người đã chuẩn bị, cậu ta sẽ chọn ra một đoạn ~[l;r]~ sao cho tổng ba số bất kì trong đoạn trừ hiệu của ~r~ và ~l~ là lớn nhất. Nói cách khác, chọn ~2~ số ~l~ và ~r~ sao cho tồn tại ~3~ số ~i_1, i_2, i_3~ thỏa ~1 \le l \le i_1 \lt i_2 \lt i_3 \le r \le n~ và biểu thức ~a_{i_1} + a_{i_2} + a_{i_3} - (r - l)~ có giá trị lớn nhất.

Nhưng vì ~Capoo~ và những người bạn đã quyết định dãy số sẽ tặng rất gần ngày sinh nhật nên mèo ta không thể thực hiện kịp kế hoạch của mình. ~Capoo~ tha thiết nhờ bạn giúp sức bằng cách gợi ý cho mèo ta giá trị lớn nhất của biểu thức trên.

Dữ liệu vào

• Dòng thứ nhất gồm một số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương.

Kết quả ra

Gồm một dòng chứa số nguyên duy nhất là kết quả bài toán.

Ràng buộc

• Subtask ~1~ (~20\%~): ~n \le 20~.
• Subtask ~2~ (~20\%~): ~n \le 2\times 10^2~.
• Subtask ~3~ (~20\%~): ~n \le 3\times 10^3~.
• Subtask ~4~ (~40\%~): ~n \le 2\times 10^5~.
• Trong tất cả các subtask có ~a_i \le 10^8~.

Ví dụ 1

Dữ liệu

5
5 1 4 2 3

Kết quả

8

Giải thích

Chọn ~l~, ~r~ tương ứng là ~1~ và ~3~, chọn ~i_1 = 1~, ~i_2 = 2~, ~i_3 = 3~.

Ta có ~a_{i_1} + a_{i_2} + a_{i_3} - (r - l) = a_1 + a_2 + a_3 - (3 - 1) = 5 + 1 + 4 - (3 - 1) = 8~

Ví dụ 2

Dữ liệu

4
1 1 1 1

Kết quả

1

Ví dụ 3

Dữ liệu

6
9 8 7 6 5 4

Kết quả

22