Kẻ thù không đội trời chung của Farmer John, Farmer Paul, đã quyết định phá hoại thiết bị vắt sữa của Farmer John!

Thiết bị vắt sữa gồm một hàng \(N\) máy vắt sữa (\(3 \le N \le 100\,000\)), trong đó máy thứ \(i\) sản xuất \(M_i\) đơn vị sữa (\(1 \le M_i \le 10\,000\)). Farmer Paul dự định ngắt kết nối một đoạn máy liên tiếp, từ máy thứ \(i\) đến máy thứ \(j\) (\(2 \le i \le j \le N-1\)). Lưu ý rằng Farmer Paul không muốn ngắt kết nối máy đầu tiên hoặc máy cuối cùng vì như vậy âm mưu của ông sẽ quá dễ bị phát hiện. Mục tiêu của Farmer Paul là giảm thiểu sản lượng sữa trung bình của những máy còn lại. Farmer Paul dự định loại bỏ ít nhất \(1\) con bò, ngay cả khi không phá hoại gì cả sẽ có lợi hơn cho ông.

May mắn thay, Farmer John đã biết được âm mưu xấu xa của Farmer Paul và đang tự hỏi sản lượng sữa sẽ bị ảnh hưởng nghiêm trọng đến mức nào nếu âm mưu thành công. Hãy giúp Farmer John tìm sản lượng sữa trung bình nhỏ nhất của những máy còn lại nếu Farmer Paul thành công.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(M_i\).

Ràng buộc

• \(3 \le N \le 100\,000\).
• \(1 \le M_i \le 10\,000\).
• Đoạn bị ngắt kết nối phải thỏa mãn \(2 \le i \le j \le N-1\).

Dữ liệu ra

In ra giá trị trung bình nhỏ nhất Farmer Paul có thể đạt được, được làm tròn đến \(3\) chữ số sau dấu thập phân và phải luôn hiển thị đủ \(3\) chữ số sau dấu thập phân.

Ví dụ

5
5
1
7
8
2

2.667

Nguồn

USACO 2014 March Contest, Gold — Sabotage

Tác giả: Brian Dean, 2014.