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

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.