Cho số nguyên \(n\) và dãy gồm \(n\) số nguyên \(a_1, a_2, \ldots, 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.

Input

Đọc từ file văn bản TBCONG.INP gồm:

• 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, \ldots, a_n\) \((|a_i| \le 10^9)\) là các phần tử của dãy.

Output

Ghi ra file văn bản TBCONG.OUT 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.

Example

5
2 5 5 1 3

5

Scoring

• Có \(30\%\) số test với \(n \le 10^2\).
• Có \(30\%\) số test tiếp theo với \(n \le 10^3\).
• Có \(40\%\) số test còn lại với \(n \le 10^6\).