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 ≤ k ≤ 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.

Input

• Dòng 1: chứa số nguyên dương ~n (3≤n≤10^5 )~;

• Dòng 2: chứa n số nguyên ~a_1,a_2,…,a_n~ ~(0≤a_i≤10^4;i=(1,n))~.

Output

• 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.

Sample Input

5
3 1 9 2 7

Sample Output

2

Giải thích ví dụ:

• 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 và 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 và 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 và 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~.

Ràng buộc:

Có ~40%~ số test ứng với ~40%~ số điểm của bài có ~3≤n≤10^2~;

Có ~60%~ số test ứng với ~60%~ số điểm của bài có ~10^3≤n≤10^5~;