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$