Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Nhân dịp sinh nhật Vova, cô giáo đã mua ~n~ gói bánh quy nhỏ để tổ chức cho bạn ấy, gói bánh thứ ~i~ có số lượng bánh là ~a[i]~.

Như thường lệ, cô giáo đặt các gói bánh trên bàn theo hàng ngang từ gói bánh thứ nhất đến gói bánh thứ ~n~, sau đó các bạn nhỏ ăn bánh ở ~k~ gói liên tiếp đầu tiên ~(1 \le k \le n - 2)~. Trong số các gói bánh còn lại cô lấy gói bánh ít nhất để mang về làm quà cho con trai yêu quý mình, và tính tổng trung bình các gói bánh còn lại sẽ chia đều cho các bạn nhỏ trong lớp.

Các bạn nhỏ muốn tìm tất cả giá trị ~k~ sao cho tổng trung bình các gói bánh còn lại (sau khi cô giáo đã lấy gói nhỏ nhất) đạt giá trị lớn nhất.

Dữ liệu vào

• Dòng 1: chứa số nguyên dương ~n~ ~(3 \le n \le 10^5)~;
• Dòng 2: chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^4;\ i = \overline{1, n})~.

Kết quả

• Một dòng duy nhất chứa các giá trị ~k~ (sắp xếp tăng dần) tìm được.

Subtask

• Có 40 số test ứng với 40 số điểm của bài có ~3 \le n \le 10^2~;
• Có 60 số test ứng với 60 số điểm của bài có ~10^3 \le n \le 10^5~.

Sample Input 1

5
3 1 9 2 7

Sample Output 1

2

Giải thích

• Nếu các bạn nhỏ ăn ~k = 1~ gói bánh đầu tiên, còn lại 4 gói là 1 9 2 7, cô giáo sẽ lấy gói bánh 1 và 3 gói bánh còn lại tính trung bình sẽ là: ~(9 + 2 + 7) / 3 = 6~.
• Nếu các bạn nhỏ ăn ~k = 2~ gói bánh đầu tiên, còn lại 3 gói là 9 2 7, cô giáo sẽ lấy gói bánh 2 và hai gói bánh còn lại tính trung bình sẽ là ~(9 + 7) / 2 = 8~.
• Nếu các bạn nhỏ ăn ~k = 3~ gói bánh đầu tiên, còn lại 2 gói là 2 7, cô giáo sẽ lấy gói bánh 2 và một gói bánh còn lại tính trung bình sẽ là ~7 / 1 = 7~.

Như vậy: các bạn nhỏ cần ăn ~k = 2~ gói bánh đầu tiên để nhận được tổng trung bình các gói bánh còn lại (sau khi cô giáo lấy đi gói ít nhất) lớn nhất bằng ~8~.

Nguồn: CLAOJ (cookies).