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.io.*;
import java.util.*;

public class D {
public static void main(String[] args){
   new Thread(null, null, "Anshum Gupta", 99999999) {
        public void run() {
            try {
                solve();
            } catch(Exception e) {
                e.printStackTrace();
                System.exit(1);
            }
        }
    }.start();
}
static final long mxx = (long)(1e18+5);
static final int mxN = (int)(4e5+5);
static final int mxV = (int)(6e4 + 2), log = 18;
static long mod = (long)(1e9+7); //998244353;//̇
static long[]fact, inv_fact;
static final int INF = (int)1e9;
static boolean[]vis;
static ArrayList<ArrayList<Integer>> adj;
static int n, m, k, q, x, y, z, d, c = 0, root = 1;
static Integer[]p;
static int[]a;
static int rec(int l, int r) {
	int outside = Math.max(a[l-1], a[r+1]);
	int mx = 0;
	for(int i=l; i<=r; i++)mx = Math.max(mx, a[i]);
	if(l > r || mx <= outside)return 0;
	int min = INF;
	for(int i=l; i<=r; i++) min = Math.min(a[i], min);
	int cnt = min - outside;
	ArrayList<Integer> minIndices = new ArrayList<Integer>();
	for(int i=l; i<=r; i++) {
		if(a[i] == min)minIndices.add(i);
	}
	int prev = l;
	for(Integer x : minIndices) {
		cnt += rec(prev, x-1);
		prev = x+1;
	}
	cnt += rec(prev, r);
	return Math.min(cnt, r - l + 1);
}
private static boolean allequal(int l, int r) {
	for(int i=l+1; i<=r; i++) {
		if(a[l] != a[i])return false;
	}
	return true;
}
private static boolean done(int l, int r) {
	for(int i=l; i<=r; i++) {
		if(a[i] != 0)return false;
	}
	return true;
}
public static void solve() throws Exception {
	   // solve the problem here
			s = new MyScanner();
	   		out = new PrintWriter(new BufferedOutputStream(System.out), true);
//	   		out = new PrintWriter("output.txt");
	        int tc = 1;//s.nextInt();
	        while(tc-->0){
	        	n = s.nextInt();
	        	a = new int[n+2];
	        	for(int i=1; i<=n; i++)a[i] = s.nextInt();
	        	int ans = rec(1, n);
	        	out.println(ans);
	        	
	        } 
	           
	        out.flush();
	        out.close();
	}

public static PrintWriter out;
public static MyScanner s;
static class MyScanner {

    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    public MyScanner(String fileName) {
    	try {
			br = new BufferedReader(new FileReader(fileName));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
    }
    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() { return Integer.parseInt(next()); }
    long nextLong() { return Long.parseLong(next()); }
    double nextDouble() { return Double.parseDouble(next()); }
    int[] nextIntArray(int n){
    	int[]a = new int[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextInt();
    	}
    	return a;
    }
    long[] nextlongArray(int n) {
    	long[]a = new long[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextLong();
    	}
    	return a;
    }
    Integer[] nextIntegerArray(int n){
    	Integer[]a = new Integer[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextInt();
    	}
    	return a;
    }
    Long[] nextLongArray(int n) {
    	Long[]a = new Long[n];
    	for(int i=0; i<n; i++) {
    		a[i] = this.nextLong();
    	}
    	return a;
    }
    char[][] next2DCharArray(int n, int m){
    	char[][]arr = new char[n][m];
    	for(int i=0; i<n; i++) {
    		arr[i] = this.next().toCharArray();
    	}
    	return arr;
    }
    ArrayList<ArrayList<Integer>> readUndirectedUnweightedGraph(int n, int m) {
    	ArrayList<ArrayList<Integer>>adj = new ArrayList<ArrayList<Integer>>();
    	for(int i=0; i<=n; i++)adj.add(new ArrayList<Integer>());
    	for(int i=0; i<m; i++) {
    		int u = s.nextInt();
    		int v = s.nextInt();
    		adj.get(u).add(v);
    		adj.get(v).add(u);
    	}
    	return adj;
    }
    ArrayList<ArrayList<Integer>> readDirectedUnweightedGraph(int n, int m) {
    	ArrayList<ArrayList<Integer>>adj = new ArrayList<ArrayList<Integer>>();
    	for(int i=0; i<=n; i++)adj.add(new ArrayList<Integer>());
    	for(int i=0; i<m; i++) {
    		int u = s.nextInt();
    		int v = s.nextInt();
    		adj.get(u).add(v);
    	}
    	return adj;
    }
    String nextLine(){
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

 
}
