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 \le 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 \ge 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 \le n \le 5000$).

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 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

Source: codeforces | Difficulty: HARD
Tags: Greedy algorithms

Dynamic programming

Data structures

Divide and conquer


Solutions:
import sys
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))

def solve(i, j, x):
	if i > j:
		return 0
	idx = a.index(min(a[i:j + 1]), i, j + 1)
	mn = a[idx]
	case = mn - x + solve(i, idx - 1, mn) + solve(idx + 1, j, mn)
	return min(case, j - i + 1)
print(solve(0, n - 1, 0))


from sys import stdin
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
a = [0] + a
ans = n
dp = [float('inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
	nmin = float('inf')
	for j in range(i - 1, -1, -1):
		if a[j] <= nmin:
			dp[i] = min(dp[i], dp[j] + max(0, a[i] - a[j]) + (i - j - 1))
		nmin = min(nmin, a[j])
for i in range(n + 1):
	ans = min(ans, dp[i] + n - i)
print(ans)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
dp = [n] * (n * (n + 1))
dg = n + 1
mi = [0] * (n + 1)
for j in range(n + 1):
	if j > a[0]:
		break
	if j == a[0]:
		dp[j] = j
	else:
		dp[j] = j + 1
tmp = 2 * n
for j in range(n + 1):
	tmp = min(tmp, dp[j] + n - j)
	mi[j] = tmp
for i in range(1, n):
	for j in range(n, -1, -1):
		if j > a[i]:
			continue
		if j != n:
			tmp = dp[i * dg + j + 1]
		else:
			tmp = n
		if a[i] > j:
			tmp = min(tmp, dp[(i - 1) * dg + j] + 1)
		else:
			tmp = min(tmp, dp[(i - 1) * dg + j])
		if j != 0:
			if a[i] > j:
				tmp = min(tmp, mi[j - 1] + j - n + 1)
			else:
				tmp = min(tmp, mi[j - 1] + j - n)
		dp[i * dg + j] = tmp
	tmp = 2 * n
	for j in range(n + 1):
		tmp = min(tmp, dp[i * dg + j] + n - j)
		mi[j] = tmp
print(dp[(n - 1) * dg])


from sys import stdin

def input():
	return stdin.readline().strip()
n = int(input())
a = list(map(int, input().split()))

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
res = 0

@bootstrap
def dfs(l, r, base):
	if r - l < 0:
		yield 0
	if r == l:
		yield 1
	mn = min(a[l:r + 1])
	count = r - l + 1
	now = mn - base
	k = l
	for i in range(l, r + 1):
		if a[i] == mn:
			now += (yield dfs(k, i - 1, mn))
			k = i + 1
	now += (yield dfs(k, r, mn))
	yield min(count, now)
if sum(a) == 0:
	print(0)
else:
	print(dfs(0, n - 1, 0))


from sys import stdin

def input():
	return stdin.readline().strip()

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
n = int(input())
ls = list(map(int, input().split()))
res = 0

@bootstrap
def ops(start, end, curr_val):
	if start == end:
		yield 1
	if end < start:
		yield 0
	curr_min = None
	ls_min = []
	for i in range(start, end + 1):
		if curr_min is None or ls[i] < curr_min:
			curr_min = ls[i]
			ls_min = [i]
		elif ls[i] == curr_min:
			ls_min.append(i)
	res_1 = end - start + 1
	res_2 = curr_min - curr_val
	curr_idx = start
	for idx in ls_min:
		res_2 += (yield ops(curr_idx, idx - 1, curr_min))
		curr_idx = idx + 1
	res_2 += (yield ops(curr_idx, end, curr_min))
	yield min(res_1, res_2)
if sum(ls) != 0:
	print(ops(0, n - 1, 0))
else:
	print(0)


n = int(input())
arr = [int(x) for x in input().split()]
arrays = [arr]
brr = [0]
stack = [0]
ans = [0]
while stack:
	state = stack.pop()
	if state >= 0:
		arr = arrays[state]
		b = brr[state]
		n = j = len(arr)
		if n == 0:
			continue
		a = min(arr)
		stack.append(~state)
		ans.append(a - b)
		for i in reversed(range(n)):
			if arr[i] == a:
				stack.append(len(arrays))
				arrays.append(arr[i + 1:j])
				brr.append(a)
				j = i
		stack.append(len(arrays))
		arrays.append(arr[0:j])
		brr.append(a)
	else:
		s = ans.pop()
		ans[-1] += min(s, len(arrays[~state]))
print(ans[0])


import sys
from math import sqrt
from collections import defaultdict
inpt = sys.stdin.readline

def inp():
	return int(inpt())

def inlist():
	return list(map(int, inpt().split()))

def solve(l, r):
	if l >= r:
		return 0
	x = a.index(min(a[l:r]), l, r)
	mn = min(a[l:r])
	(i, j) = (0, 0)
	if l - 1 >= 0:
		i = a[l - 1]
	if r < n:
		j = a[r]
	out = max(i, j)
	return min(r - l, mn + solve(l, x) + solve(x + 1, r) - out)

def main():
	ans = solve(0, n)
	print(ans)
sys.setrecursionlimit(10000)
n = inp()
a = inlist()
main()


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType

def bootstrap(f, stack=[]):

	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

def main():
	n = iin()
	a = lin()

	@bootstrap
	def solve(left, right):
		if left > right:
			yield 0
		if left >= n or right >= n or left < 0 or (right < 0):
			yield 0
		ans = right - left + 1
		mn_pos = left
		for i in range(left, right + 1):
			x = a[i]
			if x < a[mn_pos]:
				mn_pos = i
		mn2 = a[mn_pos]
		for i in range(left, right + 1):
			a[i] -= mn2
		ans = min(ans, mn2 + (yield solve(left, mn_pos - 1)) + (yield solve(mn_pos + 1, right)))
		yield ans
	ans = solve(0, n - 1)
	ans += sum([+(i > 0) for i in a])
	print(ans)
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')

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))
main()


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def cal(l, r, h=0):
	if l >= r:
		return 0
	mn = mni = inf
	for i in range(l, r):
		if aa[i] < mn:
			mn = aa[i]
			mni = i
	return min(cal(l, mni, mn) + cal(mni + 1, r, mn) + mn - h, r - l)
inf = 10 ** 16
n = II()
aa = LI()
print(cal(0, n))


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

def calc(l, r, h):
	if l >= r:
		return 0
	m = a.index(min(a[l:r]), l, r)
	return min(r - l, a[m] - h + calc(l, m, a[m]) + calc(m + 1, r, a[m]))
print(calc(0, n, 0))


import sys
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))

def f(l, r, h):
	if l > r:
		return 0
	x = a.index(min(a[l:r + 1]), l, r + 1)
	return min(r - l + 1, a[x] - h + f(l, x - 1, a[x]) + f(x + 1, r, a[x]))
print(f(0, n - 1, 0))


import sys

def solve(l, r):
	if l >= r:
		return 0
	x = a.index(min(a[l:r]), l, r)
	mn = min(a[l:r])
	(i, j) = (0, 0)
	if l - 1 >= 0:
		i = a[l - 1]
	if r < n:
		j = a[r]
	out = max(i, j)
	return min(r - l, mn + solve(l, x) + solve(x + 1, r) - out)
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))
print(solve(0, n))


from collections import Counter
from sys import stdin, stdout

def input():
	return stdin.readline().strip()

def bootstrap(f, stack=[]):
	from collections import defaultdict
	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 ans_seg(A):
	if len(A) == 0:
		yield 0
	option1 = len(A)
	m = min(A)
	for i in range(len(A)):
		A[i] -= m
	option2 = m + (yield ans(A))
	yield min(option1, option2)

@bootstrap
def ans(A):
	last_seg = []
	segs = []
	for a in A:
		if a == 0:
			segs += [last_seg]
			last_seg = []
		else:
			last_seg += [a]
	if len(last_seg):
		segs += [last_seg]
	ret = 0
	for seg in segs:
		ret += (yield ans_seg(seg))
	yield ret
N = int(input())
S = list(map(int, input().split()))
print(ans(S))


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def output(*args):
	sys.stdout.buffer.write(('\n'.join(map(str, args)) + '\n').encode('utf-8'))

def main():
	n = int(input())
	a = list(map(int, input().split()))
	stack = [(0, n, 0)]
	dp = {}
	while stack:
		(l, r, base) = stack[-1]
		min_depth = min(a[l:r])
		if (l, r, base) not in dp:
			dp[l, r, base] = -1
			i = l
			for j in range(l, r):
				if a[j] == min_depth:
					if i < j:
						stack.append((i, j, min_depth))
					i = j + 1
			if i < r:
				stack.append((i, r, min_depth))
		else:
			(i, cost) = (l, 0)
			for j in range(l, r):
				if a[j] == min_depth:
					if i < j:
						cost += dp[i, j, min_depth]
					i = j + 1
			if i < r:
				cost += dp[i, r, min_depth]
			dp[l, r, base] = min(r - l, cost + min_depth - base)
			stack.pop()
	print(dp[0, n, 0])
main()


import sys
import threading
from sys import stdin, stdout
sys.setrecursionlimit(10 ** 9)
threading.stack_size(16 * 2048 * 2048)

def clear_the_multiset(n, a_a):
	return dfs(1, n, a_a)

def dfs(l, r, a_a):
	if l > r:
		return 0
	mval = a_a[l]
	midx = l
	mx = max(a_a[l - 1], a_a[r + 1])
	for i in range(l, r + 1):
		if mval > a_a[i]:
			mval = a_a[i]
			midx = i
	r1 = r - l + 1
	r2 = mval + dfs(l, midx - 1, a_a) + dfs(midx + 1, r, a_a) - mx
	return min(r1, r2)

def solve():
	n = int(stdin.readline())
	a_a = list(map(int, stdin.readline().split()))
	a_a.insert(0, 0)
	a_a.append(0)
	ans = clear_the_multiset(n, a_a)
	stdout.write(str(ans))
threading.Thread(target=solve).start()


import os
import sys
from io import BytesIO, IOBase
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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
import sys
sys.setrecursionlimit(100000)
n = N()
a = RLL()

def clear(l, r, last):
	if l == r:
		return 0
	res = r - l
	m = min(a[l:r])
	tmp = m - last
	s = l
	for i in range(l, r):
		if a[i] == m:
			tmp += clear(s, i, m)
			s = i + 1
	tmp += clear(s, r, m)
	return min(res, tmp)
s = 0
ans = 0
for i in range(n):
	if a[i] == 0:
		ans += clear(s, i, 0)
		s = i + 1
ans += clear(s, n, 0)
print(ans)


import sys
from math import sqrt
from collections import defaultdict
inpt = sys.stdin.readline

def inp():
	return int(inpt())

def inlist():
	return list(map(int, inpt().split()))

def instr():
	s = inpt()
	return list(s[:len(s) - 1])

def invr():
	return map(int, inpt().split())

class Graph:

	def __init__(self, n):
		self.n = n
		self.graph = defaultdict(list)
		self.marked = defaultdict(int)

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def dfs(self, u):
		self.marked[u] = 1
		for i in self.graph[u]:
			if self.marked[i] == 0:
				self.dfs(i)

def solve(a, l, r):
	if l >= r:
		return 0
	x = a.index(min(a[l:r]), l, r)
	mn = min(a[l:r])
	(i, j) = (0, 0)
	if l - 1 >= 0:
		i = a[l - 1]
	if r < n:
		j = a[r]
	out = max(i, j)
	return min(r - l, mn + solve(a, l, x) + solve(a, x + 1, r) - out)

def main():
	a = inlist()
	ans = solve(a, 0, n)
	print(ans)
sys.setrecursionlimit(10000)
n = inp()
main()


from types import GeneratorType

def bootstrap(f, stack=[]):

	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
n = int(input())
l = list(map(int, input().split()))

@bootstrap
def wynik(l):
	n = len(l)
	m = min(l)
	odp1 = n - l.count(0)
	odp2 = m
	if m > 0:
		for i in range(n):
			l[i] -= m
	tablice = []
	cyk = []
	for i in range(n):
		if l[i] != 0:
			cyk.append(l[i])
		elif cyk:
			tablice.append(cyk)
			cyk = []
	if cyk:
		tablice.append(cyk)
	for ta in tablice:
		yy = (yield wynik(ta))
		odp2 += yy
	yield min(odp1, odp2)
print(wynik(l))


from math import log2, inf

class SegmentTree:

	def __init__(self, array, func=max):
		self.n = len(array)
		self.size = 2 ** (int(log2(self.n - 1)) + 1) if self.n != 1 else 1
		self.func = func
		self.default = 0 if self.func != min else inf
		self.data = [self.default] * (2 * self.size)
		self.process(array)

	def process(self, array):
		self.data[self.size:self.size + self.n] = array
		for i in range(self.size - 1, -1, -1):
			self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

	def query(self, alpha, omega):
		if alpha == omega:
			return self.data[alpha + self.size]
		res = self.default
		alpha += self.size
		omega += self.size + 1
		while alpha < omega:
			if alpha & 1:
				res = self.func(res, self.data[alpha])
				alpha += 1
			if omega & 1:
				omega -= 1
				res = self.func(res, self.data[omega])
			alpha >>= 1
			omega >>= 1
		return res

	def update(self, index, value):
		index += self.size
		self.data[index] = value
		index >>= 1
		while index:
			self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
			index >>= 1
import os
import sys
from io import BytesIO, IOBase
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')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
import sys
sys.setrecursionlimit(10 ** 5)
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	di = {}
	for i in range(n):
		if a[i] not in di:
			di[a[i]] = []
		di[a[i]] += [i]
	for i in di:
		di[i] = di[i][::-1]
	st = SegmentTree(a, func=min)

	def f(i, j, k=0):
		if i > j:
			return 0
		mi = st.query(i, j)
		index = di[mi].pop()
		return min(j - i + 1, mi - k + f(i, index - 1, max(mi, k)) + f(index + 1, j, max(mi, k)))
	print(f(0, n - 1))


import sys
input = sys.stdin.readline
from collections import defaultdict
(N,) = map(int, input().split())
X = list(map(int, input().split()))
stack = [(0, N)]
d = defaultdict(set)
vlist = []
MN = defaultdict(int)
MN[0, N] = min(X)
while stack:
	(vl, vr) = stack.pop()
	vlist.append((vl, vr))
	mn = min(X[vl:vr])
	for idx in range(vl, vr):
		if X[idx] == mn:
			break
	(rl, rr) = ((vl, idx), (idx + 1, vr))
	if vl != idx:
		stack.append(rl)
		d[vl, vr].add(rl)
		MN[rl] = min(X[vl:idx]) - mn
	if idx + 1 != vr:
		stack.append(rr)
		d[vl, vr].add(rr)
		MN[rr] = min(X[idx + 1:vr]) - mn
dp = dict()
for (vl, vr) in vlist[::-1]:
	tmp = MN[vl, vr]
	for (ul, ur) in d[vl, vr]:
		tmp += dp[ul, ur]
	tmp = min(vr - vl, tmp)
	dp[vl, vr] = tmp
print(dp[0, N])


import random
import sys
sys.setrecursionlimit(100000)
n = int(input())
a = list(map(int, input().split()))
c = 0

def find(l, r, h):
	global c
	c += 1
	if l > r:
		return 0
	m = a[l]
	x = l
	for i in range(l, r + 1):
		if a[i] < m:
			m = a[i]
			x = i
	return min(r - l + 1, a[x] - h + find(l, x - 1, a[x]) + find(x + 1, r, a[x]))
print(find(0, n - 1, 0))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def rec(l, r, sub):
	if l >= r:
		return 0
	m = a.index(min(a[l:r]), l, r)
	return min(r - l, a[m] - sub + rec(l, m, a[m]) + rec(m + 1, r, a[m]))
n = int(input())
a = list(map(int, input().split()))
print(rec(0, n, 0))


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, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
INF = float('inf')
mod = int(1000000000.0) + 7
from types import GeneratorType

def bootstrap(f, stack=[]):

	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 cal(l, r, val):
	if r - l < 0:
		yield 0
		return
	min1 = min(a[l:r + 1])
	ans = min1 - val
	k = l - 1
	for i in range(l, r + 1):
		if a[i] == min1:
			ans += (yield cal(k + 1, i - 1, min1))
			k = i
	ans += (yield cal(k + 1, r, min1))
	yield min(r - l + 1, ans)
n = int(data())
a = mdata()
out(cal(0, n - 1, 0))


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
sys.setrecursionlimit(200000000)
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
n = int(input())
A = alele()
dp = {}

def fun(l, r, h):
	if l > r:
		return 0
	if dp.get((l, r, h), -1) != -1:
		return dp[l, r, h]
	m = min(A[l:r + 1])
	pos = None
	for i in range(l, r + 1):
		if A[i] == m:
			pos = i
			break
	dp[l, r, h] = min(r - l + 1, A[pos] - h + fun(l, pos - 1, A[pos]) + fun(pos + 1, r, A[pos]))
	return dp[l, r, h]
print(fun(0, n - 1, 0))


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	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
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	n = N()
	a = RLL()
	dp = [[n] * (n + 2) for i in range(n)]
	for i in range(min(a[0], n), -1, -1):
		dp[0][i] = min(dp[0][i + 1], i + (a[0] > i))
	for i in range(1, n):
		for j in range(min(n, a[i]), -1, -1):
			dp[i][j] = min(dp[i][j + 1], dp[i - 1][j] + (a[i] > j))
			if j > a[i - 1]:
				dp[i][j] = min(dp[i][j], dp[i - 1][a[i - 1]] + j - a[i - 1] + (a[i] > j))
	print(min(dp[-1]))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(5010)
n = int(input())
A = list(map(int, input().split()))
DICT = dict()

def dfs(x, y):
	if x == y:
		return []
	MIN = min(A[x:y])
	for i in range(x, y):
		A[i] -= MIN
	ANS = []
	NOW = x
	for i in range(x, y):
		if A[i] == 0:
			if NOW != i:
				ANS.append((NOW, i))
			NOW = i + 1
	if NOW != y:
		ANS.append((NOW, y))
	DICT[x, y] = (ANS, MIN)
	return ANS
Q = [(0, n)]
TOP = []
while Q:
	(x, y) = Q.pop()
	TOP.append((x, y))
	Q += dfs(x, y)
ANSDICT = dict()
for (x, y) in TOP[::-1]:
	A = y - x
	B = DICT[x, y][1]
	for (z, w) in DICT[x, y][0]:
		B += ANSDICT[z, w]
	ANSDICT[x, y] = min(A, B)
print(ANSDICT[0, n])


import io
import os
import sys
import threading
sys.setrecursionlimit(10 ** 5)

def solve(N, A):

	def getBest(lo, hi, threshold):
		ans = 0
		i = -1
		for j in range(lo, hi):
			x = A[j]
			if x > threshold:
				if i == -1:
					i = j
					mn = x
				else:
					mn = min(mn, x)
			else:
				if i != -1:
					v = j - i
					h = mn - threshold + getBest(i, j, mn)
					ans += min(v, h)
				i = -1
		if i != -1:
			j = hi
			v = j - i
			h = mn - threshold + getBest(i, j, mn)
			ans += min(v, h)
		return ans
	return getBest(0, N, 0)

def main():
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
	(N,) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	ans = solve(N, A)
	print(ans)
threading.stack_size(1 << 24)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


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

def calc(l, r, base):
	if l > r:
		return 0
	mn = min(a[l:r + 1])
	ans = mn - base
	L = l
	for i in range(l, r + 1):
		if a[i] == mn:
			ans += calc(L, i - 1, mn)
			L = i + 1
	ans += calc(L, r, mn)
	return min(ans, r - l + 1)
print(calc(0, n - 1, 0))


import io
import os
import sys
sys.setrecursionlimit(10 ** 5)
from types import GeneratorType

def bootstrap(f, stack=[]):

	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

def solve(N, A):

	@bootstrap
	def getBest(lo, hi, threshold):
		ans = 0
		i = -1
		for j in range(lo, hi):
			x = A[j]
			if x > threshold:
				if i == -1:
					i = j
					mn = x
				else:
					mn = min(mn, x)
			else:
				if i != -1:
					v = j - i
					temp = (yield getBest(i, j, mn))
					h = mn - threshold + temp
					ans += min(v, h)
				i = -1
		if i != -1:
			j = hi
			v = j - i
			temp = (yield getBest(i, j, mn))
			h = mn - threshold + temp
			ans += min(v, h)
		yield ans
	return getBest(0, N, 0)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


import sys
input = sys.stdin.readline
INF = 10 ** 5
n = int(input())
a_raw = [int(item) for item in input().split()]
a = []
cnt = 0
for item in a_raw:
	if item >= n:
		cnt += 1
	else:
		a.append(item)
nn = len(a)
dp = [[INF] * n for _ in range(nn + 1)]
dp[0][0] = cnt
for (i, item) in enumerate(a):
	for j in range(n):
		if dp[i][j] == INF:
			continue
		if item > j:
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1)
		dp[i + 1][item] = min(dp[i + 1][item], dp[i][j] + max(0, item - j))
print(min(dp[-1]))


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

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def check(s, n, v):
	for i in range(n):
		if s[i:i + n].count(v) == 0:
			return False
	return True

def solve():
	n = mint()
	a = list(mints())
	a.append(0)
	dp = [int(1e+18)] * (n + 2)
	dp[0] = 0
	for i in range(1, n + 2):
		d = int(1e+18)
		s = 0
		z = a[i - 1]
		for j in range(i - 2, -2, -1):
			if a[j] < z:
				z = a[j]
			d = min(d, s + max(a[j] - z, 0) + dp[j + 1])
			s += 1
		dp[i] = d
	print(dp[n + 1])
solve()