题解说是考察分治或动态规划
As a teammate lunch eliminator, Quasrain takes all foods before his teammates found them in every contest. In the latest contest, there are N kinds of foods on the table. The number of each kind of food is .
Now Quasrain has two kinds of bite to eat them all.
choose two integers L and R(L <= R) then eat one from each kind of food in [L, R] with a single bite. This requires that each kind of food in [L, R] is at least one.
choose a kind K, then eat up all of food of kind K, also in a single bite. This also requires that this kind of food is at least one.
To avoid being spotted and killed, Quasrain wants to know the minimum operations for him to eat all the food.
Input
Multi testcases.
For each testcase, the first line contains one integer N (1<=N<=5000)
The second line contains N integers a1,a2...0<ai<10^9
Output
For each testcase, print one integer as the answer.
Sample Input
4
1 4 1 1
5
1 0 1 0 1
Sample Output
2
3