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.lang.reflect.Array;
import java.math.BigInteger;
import java.text.DateFormat;
import java.text.Format;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.time.LocalDateTime;
import java.util.*;
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class file {



    private static final Scanner sc = new Scanner(System.in);
    private static String s;
    private static int[] arr;
    private static HashSet<Long> set;
    private static HashMap<Character, Integer> cmap;
    private static Map<Long, Long> Lmap;
    private static Map<Integer, Integer> map;
    private static Stack<Integer> stk;
    private static ArrayList<Integer>[] graph;
    private static boolean[] visited;
    private static ArrayList<Integer> list;
    private static ArrayList<Long> Llist;

    private static final int MOD = 1000000007;

    //find max of array
    private static int findMax(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int x : arr) {
            max = Math.max(x, max);
        }
        return max;
    }

    // print an array
    private static void printArray(int[] arr) {
        for (int x : arr) {
            System.out.print(x + " ");
        }
        System.out.println();
    }

    //DFS
    private static int dfs(int curr, int prev) {
        int count = 1;
        for (int next : graph[curr]) {
            if (next==prev) continue;
            long new_count = dfs(next, curr);
            Llist.add(new_count* (graph.length - new_count));
            count += new_count;
        }
        return count;
    }

    private static int min_index(int first, int last) {
        int ind = 0, min = Integer.MAX_VALUE;
        for (int i = first; i <= last; i++) {
            if (arr[i] < min) {
                min = arr[i];
                ind = i;
            }
        }
        return ind;
    }

    private static long recurse(int first, int last) {
        int ind = min_index(first, last);
        int min = arr[ind];
        if (first > last) {
            return 0;
        } else {
            return Math.min(last-first + 1, recurse(first, ind - 1) + recurse(ind + 1, last) + min - Math.max(arr[first - 1], arr[last + 1]));
        }
    }

    private static void foo(int testCase) {
        int n = sc.nextInt();
        arr = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(recurse(1, n));
    }



    public static void main(String[] args) throws IOException {
        foo(0);
        /*
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            foo(i);
        }
        */

    }
}