Bizon the Champion isn't just attentive, he also is very hardworking.

Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height of a_{i} meters.

Bizon the Champion bought a brush in the shop, the brush's width is 1 meter. He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 5000) — the number of fence planks. The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single integer — the minimum number of strokes needed to paint the whole fence.


-----Examples-----
Input
5
2 2 1 2 1

Output
3

Input
2
2 2

Output
2

Input
1
5

Output
1



-----Note-----

In the first sample you need to paint the fence in three strokes with the brush: the first stroke goes on height 1 horizontally along all the planks. The second stroke goes on height 2 horizontally and paints the first and second planks and the third stroke (it can be horizontal and vertical) finishes painting the fourth plank.

In the second sample you can paint the fence with two strokes, either two horizontal or two vertical strokes.

In the third sample there is only one plank that can be painted using a single vertical stroke.

Difficulty: interview

Starter code:

Solutions:
import sys
n=0;
inp=[];
tree=[];#stores the index of min in range(i,j)

def build(node,i,j):
    if(i>j):
        return;
    if(i==j):
        tree[node]=int(i);
        return;
    mid=int( (i+j)/2 );

    build(2*node,i,mid)
    build(2*node+1,mid+1,j)
    if( inp[ tree[2*node] ] < inp[ tree[2*node+1] ] ):
        tree[node]= tree[2*node];
    else:
        tree[node]=tree[2*node+1]

def RMQ(node,i,j,l,r):#return  index of minimum in range i,j #r,l is current range
    if( (i<=l) and (r<=j) ):
        return tree[node];

    if( (i>r) or (j<l) ):
        return n;

    mid=int((l+r)/2);

    a=RMQ(2*node,   i, j, l ,    mid);#     j,l,mid);
    b=RMQ(2*node+1, i, j, mid+1, r);

    if( inp[a] < inp[b]):
        return a;
    else:
        return b;

def inputArray():
    A=str(input()).split();
    return list(map(int,A));


def solve(a,b,ht):
    if(a>b):
        return 0;
    mn=RMQ(1,a,b,0,n-1);
    op1=b-a+1
    op2=solve(a,mn-1 , inp[mn] ) + solve(mn+1,b, inp[mn] ) + inp[mn]-ht ;
    return min(op1,op2);


if( __name__ == "__main__"):
    n=int( input() );
    inp=inputArray();
    inp.append(1000*1000*1000+10);
    
    sys.setrecursionlimit(10000)
    #build RMQ array
    tree=[ int(n) for x in range(4*n+10) ];
    build(1,0,n-1);

    print(( solve(0,n-1,0) ));


import sys
n=0;
inp=[];
tree=[];#stores the index of min in range(i,j)

def build(node,i,j):
    if(i>j):
        return;
    if(i==j):
        tree[node]=int(i);
        return;
    mid=int( (i+j)/2 );

    build(2*node,i,mid)
    build(2*node+1,mid+1,j)
    if( inp[ tree[2*node] ] < inp[ tree[2*node+1] ] ):
        tree[node]= tree[2*node];
    else:
        tree[node]=tree[2*node+1]

def RMQ(node,i,j,l,r):#return  index of minimum in range i,j #r,l is current range
    if( (i<=l) and (r<=j) ):
        return tree[node];

    if( (i>r) or (j<l) ):
        return n;

    mid=int((l+r)/2);

    a=RMQ(2*node,   i, j, l ,    mid);#     j,l,mid);
    b=RMQ(2*node+1, i, j, mid+1, r);

    if( inp[a] < inp[b]):
        return a;
    else:
        return b;

def inputArray():
    A=str(input()).split();
    return list(map(int,A));


def solve(a,b,ht):
    if(a>b):
        return 0;
    mn=RMQ(1,a,b,0,n-1);
    op1=b-a+1
    op2=solve(a,mn-1 , inp[mn] ) + solve(mn+1,b, inp[mn] ) + inp[mn]-ht ;
    return min(op1,op2);


if( __name__ == "__main__"):
    n=int( input() );
    inp=inputArray();
    inp.append(1000*1000*1000+10);
    
    sys.setrecursionlimit(10000)
    #build RMQ array
    tree=[ int(n) for x in range(4*n+10) ];
    build(1,0,n-1);

    print( solve(0,n-1,0) );

import sys
sys.setrecursionlimit(10000)

s, n = 1, int(input())
t = [(q, i) for i, q in enumerate(map(int, input().split()))]

e = (2e9, 0)
while s < n: s <<= 1
h = [e] * s + t + [e] * (s - n)

k = s - 1
while k:
    j = k << 1
    h[k] = min(h[j], h[j + 1])
    k -= 1

def f(a, l, r):
    if r - l < 1: return 0
    if r - l < 2: return int(t[l][0] != a)
    p, q = [(s, l, r)], e
    while p:
        k, u, v = p.pop()
        if u < v:
            if u & 1:
                q = min(q, h[k + u])
                u += 1
            if v & 1:
                q = min(q, h[k + v - 1])
            p.append((k >> 1, u >> 1, v >> 1))
    b, m = q
    d, n = b - a, r - l
    return min(n, d + f(b, l, m) + f(b, m + 1, r)) if d < n else n

print(f(0, 0, n))

import sys

n=0;

inp=[];

tree=[];#stores the index of min in range(i,j)



def build(node,i,j):

    if(i>j):

        return;

    if(i==j):

        tree[node]=int(i);

        return;

    mid=int( (i+j)/2 );



    build(2*node,i,mid)

    build(2*node+1,mid+1,j)

    if( inp[ tree[2*node] ] < inp[ tree[2*node+1] ] ):

        tree[node]= tree[2*node];

    else:

        tree[node]=tree[2*node+1]



def RMQ(node,i,j,l,r):#return  index of minimum in range i,j #r,l is current range

    if( (i<=l) and (r<=j) ):

        return tree[node];



    if( (i>r) or (j<l) ):

        return n;



    mid=int((l+r)/2);



    a=RMQ(2*node,   i, j, l ,    mid);#     j,l,mid);

    b=RMQ(2*node+1, i, j, mid+1, r);



    if( inp[a] < inp[b]):

        return a;

    else:

        return b;



def inputArray():

    A=str(input()).split();

    return list(map(int,A));





def solve(a,b,ht):

    if(a>b):

        return 0;

    mn=RMQ(1,a,b,0,n-1);

    op1=b-a+1

    op2=solve(a,mn-1 , inp[mn] ) + solve(mn+1,b, inp[mn] ) + inp[mn]-ht ;

    return min(op1,op2);





if( __name__ == "__main__"):

    n=int( input() );

    inp=inputArray();

    inp.append(1000*1000*1000+10);

    

    sys.setrecursionlimit(10000)

    #build RMQ array

    tree=[ int(n) for x in range(4*n+10) ];

    build(1,0,n-1);



    print(( solve(0,n-1,0) ));



# Made By Mostafa_Khaled


import sys
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))

# 3 3 1 2 1
# -> [2, 2], [1]

def painting(left, right, arr, height):
  # find min:
  if left >= right:
    return 0
  
  min_height = min(arr[left:right])
  split = left + arr[left:right].index(min_height)

  count_horizontal = min_height - height
  count_vertical = right - left

  return min(count_vertical, 
  count_horizontal + painting(left, split, arr, min_height) + painting(split + 1, right, arr, min_height))
  
print(painting(0, len(a), a, 0))


import sys
sys.setrecursionlimit(10000)


def painting_fence(fence, cut):
	n = len(fence)
	if n == 0: return 0
	min_i = fence.index(min(fence))
	min_h = fence[min_i]
	ans = min_h-cut+painting_fence(fence[:min_i], min_h)+painting_fence(fence[min_i + 1:], min_h)
	return min(ans, n)

def main():
	_ = int(input())
	fence = list(map(int, input().split()))
	print(painting_fence(fence, 0))

def __starting_point():
	main()
__starting_point()

import sys
oo=1000000000000
ar=[]
def solve(l, r, val):
	if(r<l): return 0
	indx=l+ar[l:r+1].index(min(ar[l:r+1]))
	tot=r-l+1
	cur=ar[indx]-val+solve(l, indx-1, ar[indx])+solve(indx+1, r, ar[indx])
	return min(tot, cur)
sys.setrecursionlimit(10000)
n=int(input())
ar=list(map(int, input().split()))
print(solve(0, n-1, 0))

import sys
sys.setrecursionlimit(10**6)
 
n = int(input())
a = list(map(int, input().split()))
 
# 3 3 1 2 1
# -> [2, 2], [1]
 
def painting(left, right, arr, height):
  # find min:
  if left >= right:
    return 0
  
  min_height = min(arr[left:right])
  split = left + arr[left:right].index(min_height)
 
  count_horizontal = min_height - height
  count_vertical = right - left
 
  return min(count_vertical, 
  count_horizontal + painting(left, split, arr, min_height) + painting(split + 1, right, arr, min_height))
  
print(painting(0, len(a), a, 0))


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List

"""
created by shhuan at 2020/1/8 19:48

"""


def solve(A, left, right):
    s = [(left, right, 0)]
    memo = {}
    while s:
        l, r, ph = s.pop()
        h = min(A[l: r+1])
        n = r - l + 1
        if h - ph >= n:
            memo[(l, r)] = n
            continue

        i, j = l, l
        t = []
        while j <= r:
            if A[j] == h:
                if i < j:
                    t.append((i, j - 1, h))
                i = j + 1
            j += 1
        if i <= r:
            t.append((i, r, h))

        if any([(v[0], v[1]) not in memo for v in t]):
            s.append((l, r, ph))
            s.extend(t)
        else:
            memo[(l, r)] = min(n, h - ph + sum([memo[(v[0], v[1])] for v in t] or [0]))

    return memo[left, right]


N = int(input())
A = [int(x) for x in input().split()]
print(solve(A, 0, N-1))


import sys

sys.setrecursionlimit(1000000)
n = int(input())
A = list(map(int, input().split()))

def Analyze(left, right, counted_height):
    if left >= right:
        return 0
    min_height = min(A[left:right])
    equinox = left + A[left:right].index(min_height)
    count_isHorizontal = min_height - counted_height
    count_isVertical = right - left
    return min(count_isVertical, 
    count_isHorizontal + Analyze(left, equinox, min_height) + Analyze(equinox+1, right, min_height))

print(Analyze(0, n, 0))



n = int(input())
t = [int(x) for x in input().split()]
t.insert(0, -1)

dp = [0] * (n+3)
dp[1] = t[1]

for i in range(2, n+1):
	#albo wszystkie na lewo sa pionowe
	dp[i] = t[i] + (i-1)
	#albo na lewo jest jakis poziomy
	smallest = t[i] #najmniejszy napotkany
	for j in range(i-1, 0, -1):
		#zakladam ze j jest ostatnim poziomym
		smallest = min(smallest, t[j])
		tmp = (dp[j] + (i-j-1) + (t[i] - smallest))
		dp[i] = min(dp[i], tmp)

res = n #kiedy wszystkie sa pionowe
for i in range(1, n+1):
	#i-ty jest ostanim poziomym
	res = min(res, dp[i] + (n-i))
print(res) 


from sys import setrecursionlimit
import threading


def main():
    n = int(input())

    a = [int(x) for x in input().split()]
    if a[0] < a[-1]:
        a = a[::-1]
    mem = [{} for x in range(n)]

    def strokes(ind,height):
        if ind >= n:
            return 0
        if height in mem[ind]:
            return mem[ind][height]
        if height >= a[ind]:
            mem[ind][height] = strokes(ind+1,a[ind])
            return mem[ind][height]
        else:
            one = strokes(ind+1,height)+1
            two = strokes(ind+1,a[ind]) + a[ind]-height
            mem[ind][height] = min(one,two)
            return mem[ind][height]

    print(strokes(0,0))
    
setrecursionlimit(10000)
threading.stack_size(10**8)
t = threading.Thread(target=main)
t.start()
t.join()


n = int(input()) + 1
l = list(map(int, input().split())) + [0]
out = 0

q = []
for v in l:
    if v == 0:
        dp = []
        n = len(q)
        for i in range(n):
            curr = q[i] + i
            smol = q[i]
            for j in range(i - 1, -1, -1):
                smol = min(q[j], smol)
                diff = q[i] - smol
                curr = min(curr, diff + dp[j] + i - j - 1)
            dp.append(curr)
                
        real = [n - i + dp[i] - 1 for i in range(n)] + [n]
        out += min(real)
        q = []
    else:
        q.append(v)
print(out)


n = int(input()) + 1
l = list(map(int, input().split())) + [0]
out = 0

q = []
for v in l:
    if v == 0:
        dp = []
        n = len(q)
        for i in range(n):
            curr = q[i] + i
            smol = q[i]
            for j in range(i - 1, -1, -1):
                smol = min(q[j], smol)
                diff = q[i] - smol
                curr = min(curr, diff + dp[j] + i - j - 1)
            dp.append(curr)
                
        real = [n - i + dp[i] - 1 for i in range(n)] + [n]
        out += min(real)
        q = []
    else:
        q.append(v)
print(out)


import sys
import threading
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
threading.stack_size(16*2048*2048)
n=int(input())
a=[int(i) for i in input().split() if i!='\n']
a.insert(0,0)
a.append(0)
def solve(l,r):
    if l>r:
        return(0)
    #"outside" is the minimum number obtained in the previous iteration
    #which we have to subtract from all the elements in this segment
    outside=max(a[l-1],a[r+1])
    mina=min(a[l:r+1])
    min_index=a.index(mina,l,r+1)
    return(min(r-l+1,solve(l,min_index-1)+solve(min_index+1,r)+mina-outside))
ans=solve(1,n)
sys.stdout.write(str(ans)+'\n')


from sys import stdin
import sys
g   = lambda : stdin.readline().strip()
gl  = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1e9)+7
inf = float("inf")

from sys import setrecursionlimit
import threading

def main():
	n, = gil()
	a = gil()

	def fun(a):
		ans = 0
		n = len(a)
		off = min(a) 
		for i in range(n):
			a[i] -= off
		ans += off
		# print(a, off)
		buff = []
		while a :
			if a[-1]:
				buff.append(a.pop())
			else:
				a.pop()
				if buff : ans += fun(buff)
				buff = []

		if buff : ans += fun(buff)

		return min(ans, n)

	print(fun(a))


setrecursionlimit(10000)
threading.stack_size(10**8)
t = threading.Thread(target=main)
t.start()
t.join()