Hôm nay thầy giáo quyết định ra một bài tập về tính trung bình cộng cho cả lớp làm. Đề bài yêu cầu các bạn tìm một dãy con liên tiếp sao cho trung bình cộng của dãy là lớn nhất có thể. Po là một học sinh trong lớp, vì quá ham chơi, trốn học quá nhiều nên cậu ta không giải được bài này nên cậu ấy quyết định nhờ các bạn giúp đỡ. Các bạn hãy giúp bạn ấy nhé.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~n~ ~(n≤10^5)~
• Dòng thứ hai ghi lần lượt ~n~ số nguyên ~a_1,a_2,…,a_n~ (~|a_i |≤10^9~) cho biết các số trong dãy

Kết quả

• Ghi một số nguyên duy nhất cho biết trung bình cộng của dãy tìm được.

Ví dụ:

Input

6
1 1 1 3 3 3 

Output

3