Carrot Distribution II
Chris has \(N\) bags labeled from 1 to \(N\) arranged from left to right. Each bag has some carrots in it. The villagers queue up to collect Chris' bags of carrots. Whenever a villager asks for carrots, Chris must give the smallest labeled bag. The only condition is that a villager must receive at least as many carrots as the previous villager. But this doesn't mean Chris must stop after giving enough carrots; Chris may give more carrots than necessary.
This file enlist the number of carrots in 1000 bags labelled from 1 to 1000, in that order. What is the maximum number of villagers can Chris satisfy?
Sample Input
1 2 3 4 

Sample Output
1 2 3 4 

Explanation
 For the first input, the distribution is (1) (2) (3).
 For the second input, the distribution is (1) (2) (1,2).
 For the third input, the distribution is (2) (2) (2) (2).
 For the last input, the distribution is (2,1) (3) (3).
Here is an easier version of this problem.