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

public class e1400 implements Runnable{
	
    public static void main(String[] args) {
    	try{
            new Thread(null, new e1400(), "process", 1<<26).start();
        }
        catch(Exception e){
            System.out.println(e);
        }
    }
	public void run() {
		FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		//PrintWriter out = new PrintWriter("file.out");
		Task solver = new Task();
		//int t = scan.nextInt();
		int t = 1;
		for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
		out.close();
	}

	static class Task {
		static final int oo = Integer.MAX_VALUE;
		static final long OO = Long.MAX_VALUE;

		public void solve(int testNumber, FastReader sc, PrintWriter out) {
			int N = sc.nextInt();
			int[] arr = sc.readArray(N);
			
			segt seg = new segt(N);
			seg.build(arr);
			
			out.println(recurse(0, N-1, 0, arr, seg));
		}
		
		public static long recurse(int L, int R, int currentMin, int[] arr, segt seg) {
			if(L > R) {
				return 0;
			}
			//System.out.println(L + " " + R + " " + currentMin);
			if(L == R && arr[L] > currentMin) {
				return 1;
			}
			
			tup t = seg.queryMin(L, R);
			//dbg(t.b);
			int min = t.a;
			int loc = t.b;
			if(min == currentMin) { // there is a duplicate minimum, and the array must be split at loc
				return recurse(L, loc-1, min, arr, seg) + recurse(loc+1, R, min, arr, seg);
			}
			// else : the new min is greater
			// option A: just remove everything between L and R, column by column
			long A = R - L + 1;
			
			// option B: remove <height of min> from this range (accounting for height already taken from currentMin), then recurse
			long B = (min - currentMin) + recurse(L, loc-1, min, arr, seg) + recurse(loc+1, R, min, arr, seg);
			return Math.min(A, B);
		}
		
		static class segt { // stores minimum and the location of the minimum
	        int[] t;
	        int[] loc;
	        int N;
	        public segt(int n) {
	            t = new int[4*n];
	            loc = new int[4*n];
	            N = n;
	        }
	        
	        void build(int a[]) {
	        	build(a, 1, 0, N-1);
	        }
	        
	        void build(int a[], int v, int tl, int tr) {
	            if (tl == tr) {
	                t[v] = a[tl];
	                loc[v] = tl;
	            } else {
	                int tm = (tl + tr) / 2;
	                build(a, v*2, tl, tm);
	                build(a, v*2+1, tm+1, tr);
	                if(t[v*2] < t[v*2+1]) {
	                	t[v] = t[v*2];
	                	loc[v] = loc[v*2];
	                } else {
	                	t[v] = t[v*2+1];
	                	loc[v] = loc[v*2+1];
	                }
	            }
	        }
	        
	        tup queryMin(int l, int r) {
	        	return queryMin(1, 0, N-1, l, r);
	        }
	 
	        tup queryMin(int v, int tl, int tr, int l, int r) {
	            if (l > r) {
	            	return new tup(Integer.MAX_VALUE, -1);
	            }
	            if (l == tl && r == tr)
	                return new tup(t[v], loc[v]);
	            int tm = (tl + tr) / 2;
	            tup a = queryMin(v*2, tl, tm, l, Math.min(r, tm));
	            tup b = queryMin(v*2+1, tm+1, tr, Math.max(l, tm+1), r);
	            
	            if(a.a < b.a) {
	            	return a;
	            } else {
	            	return b;
	            }
	        }
	        
	    }
	}
	
	static long modDivide(long a, long b, long MOD) {
		a %= MOD;
		return (binpow(b, MOD-2, MOD) * a) % MOD;
	}
	static long binpow(long a, long b, long m) {
		a %= m;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	static int[] reverse(int a[]) 
    { 
        int[] b = new int[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static long[] reverse(long a[]) 
    { 
        long[] b = new long[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static void sort(int[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static void sort(long[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static class tup implements Comparable<tup>, Comparator<tup>{
		int a, b;
		tup(int a,int b){
			this.a=a;
			this.b=b;
		}
		public tup() {
		}
		@Override
		public int compareTo(tup o){
			return Integer.compare(b,o.b);
		}
		@Override
		public int compare(tup o1, tup o2) {
			return Integer.compare(o1.b, o2.b);
		}
		
		@Override
	    public int hashCode() {
			return Objects.hash(a, b);
	    }
 
	    @Override
	    public boolean equals(Object obj) {
	    	if (this == obj)
                return true;
	    	if (obj == null)
                return false;
	    	if (getClass() != obj.getClass())
                return false;
	    	tup other = (tup) obj;
	    	return a==other.a && b==other.b;
	    }
	    
	    @Override
	    public String toString() {
	    	return a + " " + b;
	    }
	}
	
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static void shuffle(long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		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());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
		
		int[] readArray(int size) {
			int[] a = new int[size];
			for(int i = 0; i < size; i++) {
				a[i] = nextInt();
			}
			return a;
		}
		
		long[] readLongArray(int size) {
			long[] a = new long[size];
			for(int i = 0; i < size; i++) {
				a[i] = nextLong();
			}
			return a;
		}
	}
	
	static void dbg(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(long[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(boolean[] arr) {
		System.out.println(Arrays.toString(arr));
	}

	static void dbg(Object... args) {
        for (Object arg : args)
            System.out.print(arg + " ");
        System.out.println();
    }
}