Mạnh là ông chủ của một rạp xiếc khá nổi tiếng. Nhận thấy xiếc
khỉ đang thu hút được một lượng lớn người đến xem, Mạnh đã quyết định đầu tư
mua một số lượng lớn khỉ về để kiếm lời.
Những con khỉ trong rạp xiếc rất thích ăn chuối, chính vì thế
để dạy chúng làm xiếc, Mạnh đã chuẩn bị rất nhiều chuối cho chúng. Chuối được
chứa trong N thùng, mỗi thùng chứa 1 số lượng các quả chuối. Các thùng được
đánh số từ 1 đến N.
Các con khỉ không thích chia sẻ chuối với những con khỉ
khác, chính vì thế nên chúng chỉ chấp nhận lấy toàn bộ chuối trong 1 thùng nào
đó chứ không chịu lấy 1 lượng chuối trong mỗi thùng. Vì ở trong rạp xiếc khả
năng kiếm tiền của những con khỉ là khác nhau nên Mạnh cũng muốn chia cho chúng
1 lượng chuối khác nhau.
Việc chia các thùng chuối cho bọn khỉ được thực hiện theo thứ
tự từ thùng 1 đến thùng N, và từ con khỉ kiếm được ít tiền đến con kiếm được
nhiều tiền hơn. Tuy nhiên để đảm bảo tính công bằng, con khỉ kiếm được nhiều tiền
hơn phải nhận được không ít hơn số chuối của con khi kiếm được ít tiền hơn. Để
không lãng phí, Mạnh muốn thùng nào cũng
thuộc về ít nhất 1 con khỉ nào đó. Hãy giúp Mạnh tính xem anh ấy có thể chia
cho được tối đa bao nhiêu con khỉ.
Dữ liệu: Vào từ
file BANANA.INP gồm
- Dòng đầu tiên chứa số nguyên dương N (2 ≤ N
≤ 5000).
- Dòng tiếp theo chứa N số nguyên dương là số
lượng chuối mỗi thùng, mỗi thùng chứa từ 1 đến 109 quả chuối.
Kết quả: Ghi
ra file BANANA.OUT là số lượng con khỉ lớn nhất có thể nhận được chuối.
Ví dụ:
|
BANANA.INP
|
BANANA.OUT
|
BANANA.INP
|
BANANA.OUT
|
|
4
1 2
1 2
|
3
|
6
6 4
2 2 2 2
|
3
|
Giải thích:
Test 1: thùng 1 cho con 1, thùng 2 cho con số 2, thùng 3 4
cho con số 3.
Test 2: Thùng 1 cho con số 1, thùng 2 3 cho con số 2, thùng 4
5 6 cho con số 3.
-
40% số test với N ≤ 200.
-
30% số test với 200
-
30% số test với 2000≤ 5000
