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
Comments