You have a multiset containing several integers. Initially, it contains a_1 elements equal to 1, a_2 elements equal to 2, ..., a_n elements equal to n.

You may apply two types of operations:

  * choose two integers l and r (l ≤ r), then remove one occurrence of l, one occurrence of l + 1, ..., one occurrence of r from the multiset. This operation can be applied only if each number from l to r occurs at least once in the multiset; 
  * choose two integers i and x (x ≥ 1), then remove x occurrences of i from the multiset. This operation can be applied only if the multiset contains at least x occurrences of i. 



What is the minimum number of operations required to delete all elements from the multiset?

Input

The first line contains one integer n (1 ≤ n ≤ 5000).

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9).

Output

Print one integer — the minimum number of operations required to delete all elements from the multiset.

Examples

Input


4
1 4 1 1


Output


2


Input


5
1 0 1 0 1


Output


3
import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main
{
	PrintWriter out = new PrintWriter(System.out);
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok = new StringTokenizer("");
    String next() throws IOException {
        if (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); }
        return tok.nextToken();
    }
    int ni() throws IOException { return Integer.parseInt(next()); }
    long nl() throws IOException { return Long.parseLong(next()); }
    
    HashMap<Long,Integer>H;
    int[]A;
    int[][]B;
    
    void solve() throws IOException {
        for (int tc=1;tc>0;tc--) {
            int n=ni();
            A=new int[n+2];
            for (int i=1;i<=n;i++) A[i]=ni();
            A[0]=-1;
            A[n+1]=-1;
            Stack<Integer>S=new Stack();
            S.push(n+1);
            int[]R=new int[n+1];
            for (int i=n;i>0;i--) {
                int u=S.pop();
                while (A[u]>=A[i]) u=S.pop();
                R[i]=u;
                S.push(u);
                S.push(i);
            }
            S.clear();
            S.push(0);
            int[]L=new int[n+1];
            for (int i=1;i<=n;i++) {
                int u=S.pop();
                while (A[u]>A[i]) u=S.pop();
                L[i]=u;
                S.push(u);
                S.push(i);
            }
            
            B=new int[n+1][n+1];
            for (int i=1;i<=n;i++) B[L[i]+1][R[i]-1]=i;
            
            H=new HashMap();
            
            out.println(dp(1,n,0));
        }
        out.flush();
    }
    
    int dp(int p,int q,int t) {
        if (q<p) return 0;
        int mp=B[p][q];
        return Math.min(q-p+1,A[mp]-t+dp(p,mp-1,A[mp])+dp(mp+1,q,A[mp]));
    }
    
    /*int dp(int p,int q,int t) {
        if (q<p) return 0;
        if (p==q) {
            if (t==A[p]) return 0;
            else return 1;
        }
        if (q-p==1) {
            if (A[p]==t && A[q]==t) return 0;
            if (Math.min(A[p],A[q])==t) return 1;
            if (A[p]==t+1 && A[q]==t+1) return 1;
            else return 2;
        }
        
        int mp=B[p][q];
        long key=mp;
        key=key*10000000007L+t;
        if (H.containsKey(key)) return H.get(key);
        
        int r1=dp(p,mp-1,t)+dp(mp+1,q,t);
        if (t<A[mp])r1++;
        int r2=dp(p,mp-1,A[mp])+dp(mp+1,q,A[mp]);
        r2+=(A[mp]-t);
        int r=Math.min(r1,r2);
        H.put(key,r);
        return r;
    }*/
    
    public static void main(String[] args) throws IOException {
        new Main().solve();
    }
}