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.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class Main
{

    public static class Range
    {

        public static Range of(final int left, final int right)
        {
            return new Range(left, right);
        }

        private final int left;
        private final int right;

        public Range(final int left, final int right)
        {
            this.left = left;
            this.right = right;
        }

        public boolean isSingle()
        {
            return left == right;
        }

        public int[] min(final int[] ints)
        {
            int min = Integer.MAX_VALUE;
            int count = 0;
            for (int i = left; i <= right; i++)
            {
                final int n = ints[i];
                if (n < min)
                {
                    min = n;
                    count = 1;
                }
                else if (n == min)
                {
                    count += 1;
                }
            }
            return new int[]{min, count};
        }

        @Override
        public boolean equals(Object o)
        {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Range range = (Range) o;
            return left == range.left &&
                    right == range.right;
        }

        @Override
        public int hashCode()
        {
            return Objects.hash(left, right);
        }

        @Override
        public String toString()
        {
            return  left < right? String.format("[%d, %d]", left, right) : "[" + left + "]";
        }

        public int length()
        {
            return right - left + 1;
        }

    }

    public static void main(String[] args) throws Exception
    {
        run(args);
    }

    private static void run(String[] args) throws Exception
    {
        final var stdin = new BufferedReader(new InputStreamReader(System.in));
        final boolean develop = args.length > 0 && "develop".equals(args[0]);
        if (!develop)
            stdin.readLine();
        //
        final int[] ints =  Arrays.stream(stdin.readLine().split(" "))
                .mapToInt(Integer::valueOf)
                .toArray();
        final int answer = solve(ints);
        System.out.println(answer);
        if (develop)
            System.out.println(ints.length);
    }

    private static int[] findPositiveValue(final int[] ints)
    {
        for (int i = 0; i < ints.length; i++)
            if (ints[i] > 0)
                return new int[]{i, ints[i]};
        //
        return null;
    }

    public static int solve(final int[] ints)
    {
        return findRanges(ints).stream()
                .mapToInt(it -> solveRec(ints, it))
                .sum();
    }

    public static int solveRec(final int[] ints, final Range range)
    {
        final int result;
        if (range.isSingle())
        {
            ints[range.left] = 0;
            result = 1;
        }
        else
        {
            final int[] minCount = range.min(ints);
            final int steps = minCount[0];
            final int atLeastLength = range.length();
            int left = -1;
            int right = -1;
            int sum = steps;
            for (int i = range.left; i <= range.right; i++)
            {
                final int diff = ints[i] - steps;
                ints[i] = diff;
                final boolean headFound = left != -1;
                if (diff == 0)
                {
                    if (headFound)
                    {
                        sum += solveRec(ints, Range.of(left, right));
                        left = -1;
                        right = -1;
                    }
                }
                else
                {
                    if (!headFound)
                        left = i;
                    //
                    right = i;
                }
            }
            if (left != -1)
                sum += solveRec(ints, Range.of(left, right));
            result = min(atLeastLength, sum);
        }
        return result;
    }

    private static int min(int... ints)
    {
        return Arrays.stream(ints).min().orElse(0);
    }

    public static List<Range> findRanges(final int[] ints)
    {
        int currentLeft = -1;
        int currentRight = -1;
        final var result = new LinkedList<Range>();
        for (int i = 0; i < ints.length; i++)
        {
            final int n = ints[i];
            final boolean headFound = currentLeft != -1;
            if (n == 0)
            {
                if (headFound)
                {
                    result.add(new Range(currentLeft, currentRight));
                    currentLeft = -1;
                    currentRight = -1;
                }
            }
            else
            {
                if (!headFound)
                    currentLeft = i;
                //
                currentRight = i;
            }
        }
        //
        if (currentLeft != -1)
            result.add(new Range(currentLeft, currentRight));
        return result;
    }

}