Cho số nguyên \(n\) và dãy 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 \le n \le 10^6)\) là số phần tử của dãy số.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2... a_n\) \((|a_i| \le 10^9)\) là các phần tử của dãy.

Kết quả:

• 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

Input

5
2 5 5 1 3

Output

5

Giải thích

Xóa đi 2 dãy [1,1] và [4,5]

Ràng buộc:

• 30% test với \(n \le 10^2\)
• 30% test với \(n \le 10^3\)
• 40% test với \(n \le 10^6\)