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
// package com.company;
import java.util.*;
import java.lang.*;
import java.io.*;
//****Use Integer Wrapper Class for Arrays.sort()****
public class EX5 {
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] Args)throws Exception{
        FastReader scan=new FastReader(System.in);
        int t=1;
//        t=scan.nextInt();
        while(t-->0){
            int n=scan.nextInt();
            Map<Pair,Integer> minf=new HashMap<>();
            int[][] dp=new int[n][n];
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                Arrays.fill(dp[i],-1);
            }
            for(int i=0;i<n;i++){
                arr[i]=scan.nextInt();
            }
            out.println(recur(0,dp,arr,0,n-1,minf));
        }
        out.flush();
        out.close();
    }
    static int recur(int red,int[][] dp,int[] arr,int l,int r,Map<Pair,Integer> minf){
        if(r-l+1==1){
            if(arr[l]-red>0){
                return 1;
            }else{
                return 0;
            }
        }
        int min=Integer.MAX_VALUE;
        int mini=-1;
        Integer in=minf.get(new Pair(l,r));
        if(in!=null){
            mini=in;
            min=arr[mini];
        }else {
            for (int j = l; j <= r; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    mini = j;
                }
            }
            minf.put(new Pair(l,r),mini);
        }
        if(dp[mini][red]!=-1){
            return dp[mini][red];
        }
        min=Math.max(0,min-red);
        int ans=Integer.MAX_VALUE;
        if(min+red<arr.length){
            ans=min;
            if(l<=mini-1) {
                ans += recur( min + red, dp, arr, l, mini - 1,minf);
            }
            if(mini+1<=r) {
                ans += recur( min + red, dp, arr, mini + 1, r,minf);
            }
        }
        int temp=0;
        if(min!=0) {
            temp++;
        }
        if(l<=mini-1) {
            temp += recur( red, dp, arr,  l, mini - 1,minf);
        }
        if(mini+1<=r) {
            temp += recur( red, dp, arr,  mini + 1, r,minf);
        }
        ans=Math.min(ans,temp);
        dp[mini][red]=ans;
        return ans;
    }
    static class Pair{
        int x;
        int y;
        Pair(int x,int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pair)) return false;
            Pair key = (Pair) o;
            return x == key.x && y == key.y;
        }

        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }
    static class FastReader {

        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;

        FastReader(InputStream is) {
            in = is;
        }

        int scan() throws IOException {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }

        String next() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
        long nextLong() throws IOException {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }
}
