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: HARD
Tags: Dynamic programming

Divide and conquer

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10000)

def cantidad_de_brochazos(izq, der, altura):
	if izq > der:
		return 0
	solo_vertical = der - izq + 1
	altura_minima = min(L[izq:der + 1])
	minimo = izq + L[izq:der + 1].index(altura_minima)
	dividir_y_conquistar = L[minimo] - altura + cantidad_de_brochazos(izq, minimo - 1, L[minimo]) + cantidad_de_brochazos(minimo + 1, der, L[minimo])
	return min(solo_vertical, dividir_y_conquistar)
n = int(sys.stdin.readline())
L = list(map(int, input().split()))
sys.stdout.write(str(cantidad_de_brochazos(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 = (2000000000.0, 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 math
import queue
import sys

def Run(L, R, H):
	if L >= R:
		return 0
	Flag = True
	for i in range(L, R):
		if Fences[i] - H > 0:
			Flag = False
	if Flag == True:
		return 0
	minHigh = min(Fences[L:R]) - H
	if minHigh >= R - L:
		return R - L
	CountStroke = 0
	tempL = L
	tempR = R
	while True:
		if tempL >= tempR:
			return CountStroke
		HighL = Fences[tempL] - H
		HighR = Fences[tempR - 1] - H
		Maxhigh = max(HighL, HighR)
		if Maxhigh < tempR - tempL:
			break
		CountStroke += 1
		if Maxhigh == HighL:
			tempL += 1
			continue
		elif Maxhigh == HighR:
			tempR -= 1
	Min = tempL
	for i in range(tempL, tempR):
		if Fences[Min] > Fences[i]:
			Min = i
	tempArry = []
	for i in range(tempL, tempR):
		if Fences[i] == Fences[Min]:
			tempArry.append(i)
	Min = tempArry[len(tempArry) // 2]
	return min(R - L, CountStroke + Fences[Min] - H + Run(tempL, Min, Fences[Min]) + Run(Min + 1, tempR, Fences[Min]))
fileInput = sys.stdin
N = int(fileInput.readline())
Fences = list(map(int, fileInput.readline().split()))
Output = Run(0, N, 0)
print(Output)


import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
a = list(map(int, input().split()))

def painting(left, right, arr, height):
	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(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))


import sys, threading
sys.setrecursionlimit(600000)

def rec(left, right, off):
	if left > right:
		return 0
	mini = min(arr[left:right + 1])
	ind = arr.index(mini, left, right + 1)
	ans = mini - off
	ans += rec(left, ind - 1, mini)
	ans += rec(ind + 1, right, mini)
	return min(right - left + 1, ans)
n = int(input())
arr = list(map(int, input().split()))
print(rec(0, n - 1, 0))


import sys
n = 0
inp = []
tree = []

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):
	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)
	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)
n = int(input())
inp = inputArray()
inp.append(1000 * 1000 * 1000 + 10)
sys.setrecursionlimit(10000)
tree = [int(n) for x in range(4 * n + 10)]
build(1, 0, n - 1)
print(solve(0, n - 1, 0))


import sys

def build(i, l, r):
	if l == r:
		it[i] = l
		return it[i]
	mid = (l + r) // 2
	p1 = build(i * 2 + 1, l, mid)
	p2 = build(i * 2 + 2, mid + 1, r)
	if a[p1] > a[p2]:
		it[i] = p2
	else:
		it[i] = p1
	return it[i]

def rmq(i, l, r, L, R):
	if r < L or R < l:
		return -1
	if L <= l and r <= R:
		return it[i]
	mid = (l + r) // 2
	p1 = rmq(i * 2 + 1, l, mid, L, R)
	p2 = rmq(i * 2 + 2, mid + 1, r, L, R)
	if p1 == -1:
		return p2
	if p2 == -1:
		return p1
	if a[p1] < a[p2]:
		return p1
	return p2

def strokesNeeded(left, right, paintedHeight):
	if left > right:
		return 0
	mini = rmq(0, 0, n - 1, left, right)
	allVerticle = right - left + 1
	recursive = a[mini] - paintedHeight + strokesNeeded(left, mini - 1, a[mini]) + strokesNeeded(mini + 1, right, a[mini])
	return min(allVerticle, recursive)
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))
it = [0 for i in range(4 * 5009)]
build(0, 0, n - 1)
print(strokesNeeded(0, n - 1, 0))


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(1000000000.0) + 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
		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()


import threading
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
threading.stack_size(16 * 2048 * 2048)

def recur(l, r):
	if l > r:
		return 0
	mina = min(a[l:r + 1])
	outside = max(a[l - 1], a[r + 1])
	ind = a.index(mina, l, r + 1)
	return min(r - l + 1, recur(l, ind - 1) + recur(ind + 1, r) + mina - outside)
n = int(input())
a = [int(i) for i in input().split() if i != '\n']
a.insert(0, 0)
a.append(0)
print(recur(1, n))


def bootstrap(f, stack=[]):
	from types import GeneratorType

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def solve(p, q):
	global heights
	answer1 = q - p
	minh = heights[p]
	for i in range(p, q):
		minh = min(minh, heights[i])
	answer2 = minh
	for i in range(p, q):
		heights[i] -= minh
	(s, t) = (-1, -1)
	for i in range(p, q):
		if heights[i] != 0 and s < 0:
			s = i
		if heights[i] == 0 and s >= 0:
			t = i
			answer2 += (yield solve(s, t))
			(s, t) = (-1, -1)
		if s >= 0 and i + 1 == q:
			answer2 += (yield solve(s, q))
	yield min(answer1, answer2)
n = int(input())
height_input = input().split()
heights = [int(h) for h in height_input]
answer = solve(0, n)
print(answer)


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()


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):
	dp[i] = t[i] + (i - 1)
	smallest = t[i]
	for j in range(i - 1, 0, -1):
		smallest = min(smallest, t[j])
		tmp = dp[j] + (i - j - 1) + (t[i] - smallest)
		dp[i] = min(dp[i], tmp)
res = n
for i in range(1, n + 1):
	res = min(res, dp[i] + (n - i))
print(res)


n = int(input()) + 1
arr = list(map(int, input().split())) + [0]
(res, q) = (0, [])
for i in arr:
	if i != 0:
		q.append(i)
		continue
	dp = []
	n = len(q)
	for i in range(n):
		curr = q[i] + i
		curr_min = q[i]
		for j in range(i - 1, -1, -1):
			curr_min = min(q[j], curr_min)
			diff = q[i] - curr_min
			curr = min(curr, diff + dp[j] + i - j - 1)
		dp.append(curr)
	res += min([n - i + dp[i] - 1 for i in range(n)] + [n])
	q = []
print(res)


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 = 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')


import sys

def strokesNeeded(left, right, paintedHeight):
	if left > right:
		return 0
	mini = left + a[left:right + 1].index(min(a[left:right + 1]))
	allVerticle = right - left + 1
	recursive = a[mini] - paintedHeight + strokesNeeded(left, mini - 1, a[mini]) + strokesNeeded(mini + 1, right, a[mini])
	return min(allVerticle, recursive)
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))
print(strokesNeeded(0, n - 1, 0))


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def calc(l, r, val):
	if r < l:
		return 0
	idx = l + a[l:r + 1].index(min(a[l:r + 1]))
	yoko = r - l + 1
	cur = a[idx] - val + calc(l, idx - 1, a[idx]) + calc(idx + 1, r, a[idx])
	return min(yoko, cur)
n = int(input())
a = list(map(int, input().split()))
print(calc(0, n - 1, 0))


import sys
import itertools
sys.setrecursionlimit(10 ** 6)

class RMQ:

	def __init__(self, n):
		self.sz = 1
		self.inf = (1 << 31) - 1
		while self.sz <= n:
			self.sz = self.sz << 1
		self.dat = [[None, self.inf] for i in range(2 * self.sz - 1)]

	def update(self, idx, x):
		old_idx = idx
		idx += self.sz - 1
		self.dat[idx] = [old_idx, x]
		while idx > 0:
			idx = idx - 1 >> 1
			self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2], key=lambda x: x[1])

	def query(self, a, b):
		return self.query_help(a, b, 0, 0, self.sz)

	def query_help(self, a, b, k, l, r):
		if r <= a or b <= l:
			return (0, sys.maxsize)
		elif a <= l and r <= b:
			return self.dat[k]
		else:
			return min(self.query_help(a, b, 2 * k + 1, l, l + r >> 1), self.query_help(a, b, 2 * k + 2, l + r >> 1, r), key=lambda x: x[1])

def solve_l_r(left, right, height):
	if left > right:
		return 0
	(min_right, min_height) = rmq.query(left, right + 1)
	res = min(right - left + 1, min_height - height + solve_l_r(left, min_right - 1, min_height) + solve_l_r(min_right + 1, right, min_height))
	return res

def painting_fences():
	for (i, j) in enumerate(case_n):
		rmq.update(i, j)
	return solve_l_r(0, len(case_n) - 1, 0)
num = int(sys.stdin.readline())
case_n = list(map(int, sys.stdin.readline().split()))
rmq = RMQ(num)
assert len(case_n) == num
print(painting_fences())


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

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
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(10000)

def recursion(left, right, painted_height):
	if left >= right:
		return 0
	mini = left + a[left:right].index(min(a[left:right]))
	allVerticles = right - left
	rec = a[mini] - painted_height + recursion(left, mini, a[mini]) + recursion(mini + 1, right, a[mini])
	return min(allVerticles, rec)
n = int(input())
a = list(map(int, input().split()))
print(recursion(0, n, 0))


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()


import sys, threading
sys.setrecursionlimit(10 ** 9)
threading.stack_size(10240000)

def rec(left, right, off):
	if left > right:
		return 0
	mini = min(arr[left:right + 1])
	ind = arr.index(mini, left, right + 1)
	ans = mini - off
	ans += rec(left, ind - 1, mini)
	ans += rec(ind + 1, right, mini)
	return min(right - left + 1, ans)
n = int(input())
arr = list(map(int, input().split()))
print(rec(0, n - 1, 0))


import os, sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	(key, val) = ([[0]], [[0]])
	for i in arr:
		val.append([])
		key.append([])
		a = 10 ** 10
		for (ind, x) in enumerate(key[-2]):
			if x < i:
				key[-1].append(x)
				val[-1].append(val[-2][ind] + 1)
				a = min(a, val[-2][ind] + i - x)
			else:
				a = min(a, val[-2][ind])
		key[-1].append(i)
		val[-1].append(a)
	print(min(val[-1]))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import itertools
from random import randint

class RMQ:

	def __init__(self, n):
		self.sz = 1
		self.inf = (1 << 31) - 1
		while self.sz <= n:
			self.sz = self.sz << 1
		self.dat = [[None, self.inf] for i in range(2 * self.sz - 1)]

	def update(self, idx, x):
		old_idx = idx
		idx += self.sz - 1
		self.dat[idx] = [old_idx, x]
		while idx > 0:
			idx = idx - 1 >> 1
			self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2], key=lambda x: x[1])

	def query(self, a, b):
		return self.query_help(a, b, 0, 0, self.sz)

	def query_help(self, a, b, k, l, r):
		if r <= a or b <= l:
			return (0, sys.maxsize)
		elif a <= l and r <= b:
			return self.dat[k]
		else:
			return min(self.query_help(a, b, 2 * k + 1, l, l + r >> 1), self.query_help(a, b, 2 * k + 2, l + r >> 1, r), key=lambda x: x[1])

def solve_l_r(left, right, height):
	if left > right:
		return 0
	(min_right, min_height) = rmq.query(left, right + 1)
	res = min(right - left + 1, min_height - height + solve_l_r(left, min_right - 1, min_height) + solve_l_r(min_right + 1, right, min_height))
	return res

def painting_fences():
	for (i, j) in enumerate(case_n):
		rmq.update(i, j)
	answer = {}
	stack = [{'left': 0, 'right': len(case_n) - 1, 'height': 0, 'recursive': True, 'calc': False}]
	while stack:
		elem = stack.pop()
		(left, right, isRecursive, height, isCalc) = (elem['left'], elem['right'], elem['recursive'], elem['height'], elem['calc'])
		if left > right:
			answer[left, right] = 0
		else:
			(min_right, min_height) = rmq.query(left, right + 1)
			if isCalc:
				answer[left, right] = min(right - left + 1, min_height - height + answer[left, min_right - 1] + answer[min_right + 1, right])
			elif isRecursive:
				stack.append({'left': left, 'right': right, 'height': height, 'recursive': False, 'calc': True})
				stack.append({'left': left, 'right': min_right - 1, 'height': min_height, 'recursive': True, 'calc': False})
				stack.append({'left': min_right + 1, 'right': right, 'height': min_height, 'recursive': True, 'calc': False})
	return answer[0, len(case_n) - 1]
num = int(sys.stdin.readline())
case_n = list(map(int, sys.stdin.readline().split()))
rmq = RMQ(num)
assert len(case_n) == num
print(painting_fences())


import sys

def Build(l, r, id):
	if l == r:
		T[id] = l
		return
	m = (l + r) // 2
	Build(l, m, id * 2)
	Build(m + 1, r, id * 2 + 1)
	if a[T[id * 2]] < a[T[id * 2 + 1]]:
		T[id] = T[id * 2]
	else:
		T[id] = T[id * 2 + 1]

def Search(l, r, le, ri, id):
	if r < l:
		return n
	if r < le or l > ri:
		return n
	if l >= le and r <= ri:
		return T[id]
	m = (l + r) // 2
	m1 = Search(l, m, le, ri, id * 2)
	m2 = Search(m + 1, r, le, ri, id * 2 + 1)
	if a[m1] <= a[m2]:
		return m1
	else:
		return m2

def solve(l, r, h):
	if r < l:
		return 0
	m = Search(0, n - 1, l, r, 1)
	return min(r - l + 1, solve(l, m - 1, a[m]) + solve(m + 1, r, a[m]) + a[m] - h)

def b5_painting_fence(n, a):
	return solve(0, n - 1, 0)
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))
a.append(2 ** 31 - 1)
T = []
for i in range(4 * n + 1):
	T.append(0)
Build(0, n - 1, 1)
result = b5_painting_fence(n, a)
print(result)


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)


from sys import stdin
input = lambda : stdin.readline().strip()
lin = lambda : list(map(int, input().split()))
iin = lambda : int(input())
main = lambda : map(int, input().split())
from math import ceil, sqrt, factorial, log
from collections import deque
from bisect import bisect_left
mod = 1000000007

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while a % b != 0:
		(a, b) = (b, a % b)
	return b

def moduloinverse(a):
	return pow(a, mod - 2, mod)

def solve(we):
	n = iin()
	l = lin()
	stack = [[0, n - 1, 0]]
	d = {}
	while stack:
		(beg, end, x) = stack.pop()
		h = min(l[beg:end + 1])
		siz = end - beg + 1
		if h - x >= siz:
			d[beg, end] = siz
			continue
		(i, j) = (beg, beg)
		z = []
		while j <= end:
			if l[j] == h:
				if i < j:
					z = z + [[i, j - 1, h]]
				i = j + 1
			j += 1
		if i <= end:
			z = z + [(i, end, h)]
		if any(((k[0], k[1]) not in d for k in z)):
			stack.append([beg, end, x])
			stack = stack + z
		else:
			d[beg, end] = min(siz, h - x + sum([d[k[0], k[1]] for k in z] or [0]))
	print(d[0, n - 1])
qwe = 1
for _ in range(qwe):
	solve(_ + 1)


def checkIncline(a):
	for i in range(len(a) - 1):
		if a[i] >= a[i + 1]:
			return False
	return True

def checkDecline(a):
	for i in range(len(a) - 1):
		if a[i] <= a[i + 1]:
			return False
	return True

def recursion(a):
	if len(a) == 1:
		return 1
	if checkIncline(a):
		return len(a)
	if checkDecline(a):
		return len(a)
	min_height = min(a)
	n = len(a)
	for i in range(n):
		a[i] -= min_height
	if max(a) == 0:
		return min(min_height, n)
	rec = 0
	(i, j) = (0, 0)
	intervals = []
	for k in range(n):
		if k == n - 1 and a[k] != 0:
			intervals.append((i, k + 1))
		if a[k] == 0:
			j = k
			if i != j:
				intervals.append((i, j))
			i = k + 1
	for (i, j) in intervals:
		rec += recursion(a[i:j])
	return min(n, rec + min_height)
n = int(input())
a = list(map(int, input().split()))
a.reverse()
print(recursion(a))