Sau khi chiến thắng sau 69 ván oẳn tù tì trí tuệ và kịch tính, Ami đã chính thức loại bỏ Thánh Ngốc và XXX cả ngày để độc mã làm quen với TN. Cậu đã dành ra rất nhiều thời gian, vượt qua bao nhiêu khó khăn để làm trái tim TN phải tan chảy. ĐNLT, anh trai mưa của TN, sau khi biết chuyện lập tức thách đấu Ami bằng một bài quy hoạch động siêu khó. Đó là bài Singer trên lequydon.ntucoder.net – với dòng caption “Ami không A/C là TN không iu”. Tất nhiên với bãn lĩnh của mình, Ami đã giải ra bài này hết sức dễ dàng, làm TN rung động còn ĐNLT thì há hốc cả mồm.

          Nhưng ĐNLT đời nào chịu thua đơn giản như vậy ? Anh lại thách đố một bài toán siêu khó khác. Cho một dãy số, hãy tìm đoạn con liên tiếp của dãy số, sao cho trung bình cộng của các số trong đoạn con đó sau khi làm tròn là lớn nhất có thể. TN nghe xong bàng hoàng, nhìn ĐNLT với ánh mắt như xin anh đừng làm khó Ami nhiều như thế. Nhưng đối với Ami thì bài này cũng chẳng đáng là bao khi so với phần thưởng ngọt ngào là những buổi hẹn hò lãng mạn với TN. Ami cười nói :”Bài này có thể giải được với giới hạn gấp rưỡi đấy ĐNLT nhé”. ĐNLT không tin, thách Ami giải được với giới hạn mà ĐNLT cho là đã khó hết mức.

          Ami không muốn giải bài toán ĐNLT đưa ra vì bài này quá dễ, cậu còn phải dành thời gian để nghiên cứu rõ hơn TN để làm vui lòng cô ấy. Các bạn hãy giải giúp Ami nhé. Bài toán như sau, các bạn được cho 1 dãy số, hãy tìm một đoạn con liên tiếp của dãy số sao cho trung bình cộng của các phần tử trong đoạn con là lớn nhất có thể. Trung bình cộng của 1 dãy a₁,a₂,…a_n chính là tổng các số của dãy chia cho độ dài dãy đó. Lưu ý rằng phép làm tròn là số học (ví dụ 4.5 làm tròn là 5, 4.3 làm tròn là 4).

Input

Dòng đầu gồm 1 số nguyên dương n là chiều dài của dãy số (n <= 10000).
Dòng tiếp theo gồm n số nguyên dương a_i là giá trị của số thứ i (a_i <= 10⁹).

Output

Hãy in ra một số nguyên là kết quá của bài toán.