Câu 2: (6 đ) Trung bình cộng

Cho số nguyên ~n~ và dãy số gồm n số nguyên ~a_1, a_2, …, a_n~. Tìm cách xóa đi tối đa 2 dãy con liên tiếp không cắt nhau của dãy đó để các phần tử còn lại có trung bình cộng lớn nhất.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên dương ~n (1 ≤ n ≤ 10^6)~ là số phần tử của dãy số.

Dòng thứ hai chứa n số nguyên ~a_1, a_2, …, a_n~ ~(|ai| < 10^9)~ là các phần tử của dãy.

Kết quả:

Gồm một số nguyên duy nhất là phần nguyên trung bình cộng của các phần tử còn lại.

Ví dụ:

Input:

5
2 5 5 1 3

Output:

5

Giải thích: Xóa đi 2 dãy [1,2] và [4,5] thì trung bình cộng lớn nhất là 5.

Ràng buộc

Có 30% số test với ~n ≤ 10^2~.

Có 30% số test với ~n ≤ 10^3~.

Có 40% số test với ~n ≤ 10^6~.