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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class e {
	public static void main(String[] args) {
		FastScanner scan=new FastScanner();
		PrintWriter out=new PrintWriter(System.out);
		
		n=scan.nextInt();
		tree=new segtree(n+10);
		
		a=new int[n];
		for(int i=0;i<n;i++) {
			a[i]=scan.nextInt();
			tree.increment(i+1,i+1,a[i]);
		}
		dp=new int[n][n];
		for(int[] d:dp) Arrays.fill(d,-1);
		out.println(go(0,n-1));
		out.close();
	}
	public static int go(int l, int r) {
		if(l>r) return 0;
		if(dp[l][r]!=-1) return dp[l][r];
		
		int res=Integer.MAX_VALUE;
		
		int movesmade=0;
		if(l>0) movesmade=Math.max(movesmade,a[l-1]);
		if(r<n-1) movesmade=Math.max(movesmade,a[r+1]);
		
		int min=tree.rangeMin(1,l+1,r+1);
		int temp=min-movesmade;
		int knockdown=0;
		
		int last=-1, first=-1;
		for(int i=l;i<=r;i++) {
			if(a[i]!=min) {
				last=i;
				if(first==-1) first=i;
			}
			else if(last!=-1) {
				temp+=go(first,last);
				first=-1;
				last=-1;
			}
			
			if(a[i]-movesmade>0) knockdown++;
		}
		if(last!=-1) {
			temp+=go(first,last);
		}
		res=Math.min(res,temp);
		res=Math.min(res,knockdown);
		return dp[l][r]=res;
	}
	static int n;
	static int[] a;
	static int[][] dp;
	static segtree tree;
	
	static class segtree {
		int n;
		int[] lo, hi, min, max, sum, delta;

		segtree(int n) {
			this.n=n;
			lo=new int[4*n+1];//low end of range for each node
			hi=new int[4*n+1];//high end of range for each node
			min=new int[4*n+1];
			max=new int[4*n+1];
			sum=new int[4*n+1];
			delta=new int[4*n+1];

			init(1,0,n-1);//init for root node and it is the entire range
		}

		void init(int i, int a, int b) {
			lo[i]=a;
			hi[i]=b;

			if(a==b) return;//you are at a leaf

			int m=(a+b)/2;
			init(2*i,a,m);//recur for left child
			init(2*i+1,m+1,b);//recur for right child
		}

		//Lazy propagation (push delta to children)
		void prop(int i) {
			delta[2*i]+=delta[i];
			delta[2*i+1]+=delta[i];
			delta[i]=0;
		}

		//update range minimum
		void update(int i) {
			min[i]=Math.min(min[2*i]+delta[2*i],min[2*i+1]+delta[2*i+1]);
			max[i]=Math.max(max[2*i]+delta[2*i],max[2*i+1]+delta[2*i+1]);
			
			sum[i]=sum[2*i]+((hi[2*i]-lo[2*i]+1)*delta[2*i]);
			sum[i]+=sum[2*i+1]+((hi[2*i+1]-lo[2*i+1]+1)*delta[2*i+1]);
		}
		void increment(int a, int b, int val) {
			increment(1,a,b,val);
		}
		void increment(int i, int a, int b, int val) {
			if(hi[i]<a||lo[i]>b) return;//no cover

			if(lo[i]>=a&&hi[i]<=b) {//full cover
				delta[i]+=val;
				return;
			}

			//partial cover
			prop(i);

			increment(2*i,a,b,val);
			increment(2*i+1,a,b,val);

			update(i);
		}

		int rangeMin(int i, int a, int b) {
			if(hi[i]<a||lo[i]>b) return Integer.MAX_VALUE;//no cover

			if(lo[i]>=a&&hi[i]<=b) {//full cover
				return min[i]+delta[i];
			}

			//partial cover

			prop(i);

			int left=rangeMin(2*i,a,b);
			int right=rangeMin(2*i+1,a,b);

			update(i);

			return Math.min(left,right);
		}

		int rangeMax(int i, int a, int b) {
			if(hi[i]<a||lo[i]>b) return Integer.MIN_VALUE;//no cover

			if(lo[i]>=a&&hi[i]<=b) {//full cover
				return max[i]+delta[i];
			}

			//partial cover

			prop(i);

			int left=rangeMax(2*i,a,b);
			int right=rangeMax(2*i+1,a,b);

			update(i);

			return Math.max(left,right);
		}

		int rangeSum(int i, int a, int b) {
			if(hi[i]<a||lo[i]>b) return 0;//no cover

			if(lo[i]>=a&&hi[i]<=b) {//full cover
				return sum[i]+delta[i]*(hi[i]-lo[i]+1);
			}

			//partial cover

			prop(i);

			int left=rangeSum(2*i,a,b);
			int right=rangeSum(2*i+1,a,b);

			update(i);

			return left+right;
		}
	}
	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
 
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e){e.printStackTrace();}
		}
 
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
 
		public int nextInt() {return Integer.parseInt(next());}
 
		public long nextLong() {return Long.parseLong(next());}
 
		public double nextDouble() {return Double.parseDouble(next());}
 
		public String nextLine() {
			String line = "";
			if(st.hasMoreTokens()) line = st.nextToken();
			else try {return br.readLine();}catch(IOException e){e.printStackTrace();}
			while(st.hasMoreTokens()) line += " "+st.nextToken();
			return line;
		}
	}
}