# Carrot Distribution II

Computer Science Level pending

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 1 2 3 1 2 1 2 2 2 2 2 2 1 3 3 

Sample Output

 1 2 3 4 3 3 4 3 

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.

×