AtCoder Beginner Contest 116 - Grand Garden

In a flower bed, there are N flowers, numbered 1,2,......,N. Initially, the heights of all flowers are 0.
You are given a sequence h=\{h_1,h_2,h_3,......\} as input. You would like to change the height of Flower k to h_k for all k (1 \leq  k \leq N), by repeating the following "watering" operation:
 - Specify integers l and r. Increase the height of Flower x by 1 for all x such that l \leq x \leq r.
Find the minimum number of watering operations required to satisfy the condition.

-----Constraints-----
 - 1 \leq N  \leq 100
 - 0 \leq h_i \leq 100
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
h_1 h_2 h_3 ...... h_N

-----Output-----
Print the minimum number of watering operations required to satisfy the condition.

-----Sample Input-----
4
1 2 2 1

-----Sample Output-----
2

The minimum number of watering operations required is 2.
One way to achieve it is:
 - Perform the operation with (l,r)=(1,3).
 - Perform the operation with (l,r)=(2,4).

Difficulty: EASY

Starter code:

Solutions:
import numpy as np
N = int(input())
h = list(map(int, input().split()))
s = h[0]
for i in range(N - 1):
	if h[i] <= h[i + 1]:
		s = s + h[i + 1] - h[i]
print(s)


N = int(input())
H = list(map(int, input().split()))
print(sum((max(0, H[n] - H[n + 1]) for n in range(N - 1))) + H[-1])


n = int(input())
hh = list(map(int, input().split()))
cnt = 0
while hh.count(0) != n:
	a = [i for (i, x) in enumerate(hh) if x == 0]
	if a != []:
		for i in range(len(a) - 1):
			if a[i] + 1 != a[i + 1]:
				for j in range(a[i] + 1, a[i + 1]):
					hh[j] -= 1
				cnt += 1
		if a[0] != 0:
			for j in range(a[0]):
				hh[j] -= 1
			cnt += 1
		if a[-1] != n - 1:
			for j in range(a[-1] + 1, n):
				hh[j] -= 1
			cnt += 1
	else:
		for i in range(n):
			hh[i] -= 1
		cnt += 1
print(cnt)


n = int(input())
h = list(map(int, input().split()))
cnt = 0
status = False
for i in range(100):
	for j in range(n):
		if h[j] > 0 and status == True:
			h[j] -= 1
		elif h[j] > 0:
			cnt += 1
			h[j] -= 1
			status = True
		else:
			status = False
		if j == n - 1:
			status = False
print(cnt)


N = int(input())
h = list(map(int, input().split()))
l = 0
flag = 1
count = 0
while l < N:
	while h[l] == 0:
		l += 1
		if l == N:
			flag = 0
			break
	if flag == 1:
		if l == N - 1:
			r = N - 1
		else:
			r = l + 1
			while h[r] != 0:
				r += 1
				if r == N:
					break
			r -= 1
		for k in range(l, r + 1):
			h[k] -= 1
		count += 1
	elif flag == 0:
		break
print(count)


n = int(input())
h = list(map(int, input().split()))
h += [0]
ans = 0
for i in range(n):
	ans += max(h[i] - h[i + 1], 0)
print(ans)


N = int(input())
H = list(map(int, input().split()))
(ans, now) = (0, 0)
for h in H:
	if h > now:
		ans += h - now
	now = h
print(ans)


N = int(input())
h = list(map(int, input().split()))
ans = h[0]
for i in range(N - 1):
	if h[i] < h[i + 1]:
		ans += h[i + 1] - h[i]
print(ans)


n = int(input())
h = list(map(int, input().split()))
ans = 0
pre = 0
for i in h:
	if pre < i:
		ans += i - pre
	pre = i
print(ans)


n = int(input())
h = list(map(int, input().split()))
ans = 0
for i in range(max(h)):
	if h[0] == 0:
		zeroFlag = True
		for j in range(0, n):
			if h[j] == 0:
				zeroFlag = True
			if h[j] != 0 and zeroFlag == True:
				ans += 1
				zeroFlag = False
			if h[j] > 0:
				h[j] -= 1
	else:
		numFlag = True
		for j in range(0, n):
			if h[j] == 0:
				numFlag = True
			if h[j] != 0 and numFlag == True:
				ans += 1
				numFlag = False
			if h[j] > 0:
				h[j] -= 1
print(ans)


N = int(input())
base = 0
ans = 0
for h in list(map(int, input().split())):
	ans += max(0, h - base)
	base = h
print(ans)


N = int(input())
A = [0] + list(map(int, input().split()))
print(sum([max(A[i + 1] - A[i], 0) for i in range(N)]))


N = int(input())
h = list(map(int, input().split()))
k = 0
for i in range(N - 1):
	k += min(h[i], h[i + 1])
print(sum(h) - k)


n = int(input())
H = list(map(int, input().split()))
pre = 0
cnt = 0
for h in H:
	if h > pre:
		cnt += h - pre
	pre = h
print(cnt)


import sys
N = int(input())
h = [0] + list(map(int, input().split()))
ans = 0
for i in range(1, N + 1):
	d = h[i] - h[i - 1]
	ans += max(d, 0)
print(ans)


n = int(input())
a = list(map(int, input().split()))
r = 0
b = [a]
while True:
	d = []
	for x in b:
		m = min(x)
		r += m
		d.append([i - m for i in x])
	b = []
	for x in d:
		t = []
		for y in range(len(x)):
			if y == len(x) - 1:
				if x[y] != 0:
					t.append(x[y])
					b.append(t)
				if x[y] == 0 and x[y - 1] != 0:
					b.append(t)
			elif x[y] != 0:
				t.append(x[y])
			elif x[y] == 0:
				if len(t) != 0:
					b.append(t)
				t = []
	d = []
	for x in b:
		if len(x) <= 2:
			r += max(x)
		else:
			d.append(x)
	if len(d) == 0:
		print(r)
		return
	b = d


n = int(input())
h = list(map(int, input().split()))
cnt = 0
v = 0
for i in h:
	if i > v:
		cnt += i - v
	v = i
print(cnt)


n = int(input())
h = [0] + list(map(int, input().split())) + [0]
ans = 0
for (i, j) in zip(h, h[1:]):
	ans += max(0, j - i)
print(ans)


(n, *h) = map(int, open(0).read().split())
h += [0]
print(sum((max(h[i] - h[i + 1], 0) for i in range(n))))


n = int(input())
h = list(map(int, input().split()))
cnt = 0
for i in range(n):
	while h[i] > 0:
		h[i] -= 1
		cnt += 1
		j = 1
		while i + j < n:
			if h[i + j] >= 1:
				h[i + j] -= 1
				j += 1
			else:
				break
print(cnt)


N = int(input())
li = list(map(int, input().split()))
base = li[0]
for i in range(1, N):
	if li[i] > li[i - 1]:
		base += li[i] - li[i - 1]
print(base)


n = int(input())
h = list(map(int, input().split()))
w = 0
a = True
while a:
	mizu = False
	if sum(h) == 0:
		a = False
		break
	w += 1
	for i in range(n):
		if h[i] != 0:
			h[i] -= 1
			mizu = True
		elif mizu:
			break
print(w)


(N, *H) = map(int, open(0).read().split())
diff = [H[0]] + [abs(prv - cur) for (prv, cur) in zip(H, H[1:])] + [H[-1]]
print(sum(diff) // 2)


a = int(input())
b = list(map(int, input().split()))
b.append(0)
ans = 0
while not max(b) == 0:
	for i in range(len(b)):
		if b[i] > 0 and b[i + 1] <= 0:
			ans += 1
	b = list([x - 1 for x in b])
print(ans)


N = int(input())
H = list(map(int, input().split(' ')))
ans = H[0]
for i in range(N - 1):
	ans += max(0, H[i + 1] - H[i])
print(ans)


n = int(input())
h = list(map(int, input().split()))
w = h[0]
for i in range(n - 1):
	if h[i + 1] > h[i]:
		w += h[i + 1] - h[i]
print(w)


N = int(input())
L = [0] + list(map(int, input().split()))
L.append(0)
M = 0
for i in range(N + 1):
	if L[i + 1] > L[i]:
		M += L[i + 1] - L[i]
print(M)


i = input
i()
s = p = 0
for x in map(int, i().split()):
	s += max(x - p, 0)
	p = x
print(s)


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

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

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	N = I()
	L = LI()
	res = 0
	while True:
		add = True
		for i in range(N):
			if L[i] >= 1:
				L[i] -= 1
				if add:
					res += 1
					add = False
			else:
				add = True
		if sum(L) == 0:
			break
	print(res)

def __starting_point():
	main()
__starting_point()


N = int(input())
a = 0
t = 0
for h in map(int, input().split()):
	a += max(h - t, 0)
	t = h
print(a)


N = int(input())
L = [int(i) for i in input().split()]
L.insert(0, 0)
print(sum([L[i + 1] - L[i] for i in range(N) if L[i + 1] - L[i] > 0]))


N = int(input())
A = list(map(int, input().split()))
cur = 0
ans = 0
for i in range(N):
	if A[i] > cur:
		ans += A[i] - cur
	cur = A[i]
print(ans)


N = int(input())
h = [int(x) for x in input().split()]
ans = h[0]
for i in range(1, N):
	if h[i - 1] < h[i]:
		ans += h[i] - h[i - 1]
print(ans)


n = int(input())
h = list(map(int, input().split()))
tmp = 0
ans = 0
for i in range(n):
	if h[i] > tmp:
		ans += h[i] - tmp
	tmp = h[i]
print(ans)


N = int(input())
H = list(map(int, input().split()))
ans = H[0]
for i in range(1, N):
	a = H[i] - H[i - 1]
	if a > 0:
		ans += a
print(ans)


N = int(input())
h = list(map(int, input().split()))
c = 0
for i in range(N - 1):
	d = h[i + 1] - h[i]
	if d < 0:
		c += abs(d)
print(c + h[-1])


import math
from math import gcd, pi, sqrt
INF = float('inf')
MOD = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
import bisect
from collections import Counter, deque

def i_input():
	return int(input())

def i_map():
	return map(int, input().split())

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	N = i_input()
	H = i_list()
	H.append(0)
	ans = 0
	for i in range(len(H) - 1):
		if H[i] > H[i + 1]:
			ans += H[i] - H[i + 1]
	print(ans)

def __starting_point():
	main()
__starting_point()


N = int(input())
h = list(map(int, input().split()))
ans = 0
left = 0
for i in h:
	if i > left:
		ans += i - left
	left = i
print(ans)


n = int(input())
h = [int(i) for i in input().split()]
ans = h[0]
for i in range(1, n):
	if h[i] > h[i - 1]:
		ans += h[i] - h[i - 1]
print(ans)


import sys
sys.setrecursionlimit(10 ** 8)
ini = lambda : int(sys.stdin.readline())
inl = lambda : [int(x) for x in sys.stdin.readline().split()]
ins = lambda : sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print('\x1b[33m', *a, '\x1b[0m', **dict(file=sys.stderr, **kw))

def solve():
	n = ini()
	H = inl()

	def calc(l, r, b):
		if l >= r:
			return 0
		mh = min(H[l:r])
		if mh < b:
			return 0
		res = mh - b
		i = l
		while i < r:
			if H[i] == mh:
				res += calc(l, i, mh)
				l = i + 1
			i += 1
		res += calc(l, r, mh)
		return res
	return calc(0, n, 0)
print(solve())


N = int(input())
L = [int(i) for i in input().split()]
L.insert(0, 0)
ans = 0
for i in range(N):
	ans += max(0, L[i + 1] - L[i])
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()
n = ni()
h = na()
ans = h[0]
for i in range(1, n):
	ans += max(0, h[i] - h[i - 1])
print(ans)


N = int(input())
ls = [int(s) for s in input().split()]
ls.append(0)
a = 0
for i in range(N):
	a += max([0, ls[i] - ls[i + 1]])
print(a)


(_, *h) = map(int, open(0).read().split())
s = p = 0
for i in h:
	s += max(i - p, 0)
	p = i
print(s)


n = int(input())
h = list(map(int, input().split()))
s = sum(h)
count = 0
while s > 0:
	f = False
	for i in range(n):
		if f:
			break
		if h[i] == 0:
			continue
		for j in range(i, n):
			if h[j] == 0:
				f = True
				break
			h[j] -= 1
			s -= 1
		count += 1
		break
print(count)


(N, *h) = map(int, open(0).read().split())
ans = 0
left = 0
for i in h:
	if i > left:
		ans += i - left
	left = i
print(ans)


n = int(input())
h = list(map(int, input().split()))
ans = 0
prev = 0
for h_i in h:
	ans += max(h_i - prev, 0)
	prev = h_i
print(ans)


n = int(input())
h = list(map(int, input().split())) + [0]
s = h[0]
for i in range(n):
	s += abs(h[i + 1] - h[i])
print(s // 2)


n = int(input())
l = list(map(int, input().split()))
b = l[0]
ans = b
for i in l:
	if b <= i:
		ans += i - b
	b = i
print(ans)


n = int(input())
h = list(map(int, input().split()))
cnt = 0

def hana(h):
	nonlocal cnt
	if len(h) == 0:
		return
	if len(h) == 1:
		cnt += h[0]
		return
	m = min(h)
	cnt += m
	h = [i - m for i in h]
	while 0 in h:
		hana(h[:h.index(0)])
		h = h[h.index(0) + 1:]
	hana(h)
hana(h)
print(cnt)


N = int(input())
h = list(map(int, input().split()))
ans = h[0]
bottom = 0
for i in range(0, len(h) - 1):
	if h[i] <= h[i + 1]:
		ans += h[i + 1] - h[i]
	else:
		continue
print(ans)


n = int(input())
L = list(map(int, input().split()))
L = [0] + L
num = 0
for i in range(n):
	if L[i] <= L[i + 1]:
		num += L[i + 1] - L[i]
print(num)


N = int(input())
H = list(map(int, input().split()))
res = H[0]
for i in range(1, N):
	if H[i] > H[i - 1]:
		res += H[i] - H[i - 1]
print(res)


N = int(input())
H = list(map(int, input().split()))
ans = sum(H)
for i in range(N - 1):
	ans -= min(H[i], H[i + 1])
print(ans)


url = 'https://atcoder.jp//contests/abc116/tasks/abc116_c'

def main():
	input()
	h = list(map(int, input().split()))
	h.append(0)
	count = 0

	def start_end(h):
		s_e = [-1, -1]
		for i in range(len(h)):
			if h[i] != 0 and s_e[0] == -1:
				s_e[0] = i
			elif h[i] == 0 and s_e[0] != -1:
				s_e[1] = i
				break
		return s_e
	while True:
		s_e = start_end(h)
		if s_e[0] == -1 and s_e[1] == -1:
			print(count)
			return
		min_h = min(h[s_e[0]:s_e[1]])
		for i in range(s_e[0], s_e[1]):
			h[i] -= min_h
		count += min_h

def __starting_point():
	main()
__starting_point()


n = int(input())
h = [0] + list(map(int, input().split()))
ans = 0
for i in range(n):
	s = h[i + 1] - h[i]
	if s > 0:
		ans += s
print(ans)


import sys
import math
sys.setrecursionlimit(500000)
INF = float('inf')

def solve(h, water):
	left = 0
	while left < len(h) - 1 and h[left] == 0:
		left += 1
	right = left
	while right < len(h) and h[right] != 0:
		right += 1
	if left < right:
		h[left:right] = [i - 1 for i in h[left:right]]
	elif left == right and h[left] > 0:
		h[left] = h[left] - 1
	else:
		return water
	water = solve(h, water + 1)
	return water

def main():
	n = int(input())
	h = list(map(int, input().split()))
	return solve(h, 0)

def __starting_point():
	print(main())
__starting_point()


N = int(input())
h = list(map(int, input().split()))
h.append(0)
t = 0

def Water(n):
	nonlocal h
	while h[n] != 0:
		h[n] -= 1
		n += 1
for i in range(N):
	while h[i] != 0:
		Water(i)
		t += 1
print(t)


N = int(input())
h = list(map(int, input().split()))
cnt = h[0]
for i in range(1, N):
	cnt += max(h[i] - h[i - 1], 0)
print(cnt)


N = int(input())
(*H,) = map(int, input().split())
H = [0] + H
ans = 0
for i in range(1, N + 1):
	w = H[i] - H[i - 1]
	if w > 0:
		ans += w
print(ans)


n = int(input())
h = list(map(int, input().split()))
h.insert(0, 0)
cnt = 0
for i in range(n):
	cnt += max(h[i + 1] - h[i], 0)
print(cnt)


n = int(input())
h = list(map(int, input().split()))
s = h[0]
c = s
for i in h[1:]:
	if i > s:
		c += i - s
		s = i
	else:
		s = i
print(c)


N = int(input())
h = list(map(int, input().split()))
sw = True
temp = 0
ans = 0
for i in range(N - 1):
	if sw == True:
		if h[i] > h[i + 1]:
			ans += h[i] - temp
			sw = False
	elif h[i] < h[i + 1]:
		temp = h[i]
		sw = True
if sw == True:
	ans += h[N - 1] - temp
print(ans)


N = int(input())
H = list(map(lambda x: -int(x), input().split())) + [0]
cnt = 0
for i in range(N):
	while H[i] < 0:
		H[i] += 1
		j = i + 1
		while H[j] < 0:
			H[j] += 1
			j += 1
		cnt += 1
print(cnt)


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

def dfs(a):
	if not a:
		return 0
	cnt = 0
	while True:
		if 0 in a:
			z = [i for (i, x) in enumerate(a) if x == 0]
			cnt += dfs(a[:z[0]])
			for i in range(1, len(z)):
				cnt += dfs(a[z[i - 1] + 1:z[i]])
			cnt += dfs(a[z[-1] + 1:])
			return cnt
		else:
			a = [x - 1 for x in a]
			cnt += 1
print(dfs(h))


N = int(input())
H = list(map(int, input().split()))
ans = 0
m = 0
for h in H:
	ans += max(h - m, 0)
	m = h
print(ans)


n = int(input())
h = list(map(int, input().split()))
h = [0] + h
ans = 0
for (s, t) in zip(h[:-1], h[1:]):
	ans += max(t - s, 0)
print(ans)


N = int(input())
H = list(map(int, input().split()))
cnt = 0
for i in range(N - 1):
	cnt += min(H[i], H[i + 1])
print(sum(H) - cnt)


(n, *a) = map(int, open(0).read().split())
print(sum((max(j - i, 0) for (i, j) in zip([0] + a, a))))


N = int(input())
h = [int(i) for i in input().split()] + [0]
ans = sum((max(h[i] - h[i + 1], 0) for i in range(N)))
print(ans)


n = int(input())
f = list(map(int, input().split()))
a = f[0]
for i in range(n - 1):
	if f[i] < f[i + 1]:
		a += f[i + 1] - f[i]
print(a)


n = int(input())
h = list(map(int, input().split()))
hn = 0
c = 0
for i in h:
	if hn < i:
		c += i - hn
	hn = i
print(c)


def main():
	n = int(input())
	h = list(map(int, input().split()))
	maxh = max(h)
	cnt = 0
	for i in range(maxh, 0, -1):
		if h[0] >= i:
			cnt += 1
		for j in range(1, n):
			if h[j] >= i and h[j - 1] < i:
				cnt += 1
	print(cnt)
main()


n = int(input())
h = list(map(int, input().split()))
res = 0
while True:
	if sum(h) == 0:
		break
	i = 0
	while i < n:
		if h[i] == 0:
			i += 1
		else:
			res += 1
			while i < n and h[i] > 0:
				h[i] -= 1
				i += 1
print(res)


n = int(input())
h = list(map(int, input().split()))
H = [h]
ans = 0
while len(H) > 0:
	for e in H:
		if len(e) == 0:
			H.remove(e)
		elif 0 in e:
			a = e[:e.index(0)]
			b = e[e.index(0) + 1:]
			H.append(a)
			H.append(b)
			H.remove(e)
			if [] in H:
				H.remove([])
				if len(H) == 0:
					break
		else:
			ans += min(e)
			c = [e[j] - min(e) for j in range(len(e))]
			a = c[:c.index(0)]
			b = c[c.index(0) + 1:]
			H.append(a)
			H.append(b)
			H.remove(e)
			if [] in H:
				H.remove([])
				if len(H) == 0:
					break
		if [] in H:
			H.remove([])
			if len(H) == 0:
				break
print(ans)


n = int(input())
hl = list(map(int, input().split()))
p = sum = 0
for i in range(n):
	if p < hl[i]:
		sum += hl[i] - p
	p = hl[i]
print(sum)


N = int(input())
h = [0] + [int(x) for x in input().split()]
print(sum([x - y for (x, y) in zip(h[1:], h[:-1]) if x - y > 0]))


def f(myList):
	if len(myList) == 0:
		return 0
	else:
		tmp = min(myList)
		ans = tmp
		for i in range(len(myList)):
			myList[i] -= tmp
		newList = []
		for i in range(len(myList)):
			pop_a = myList.pop()
			if pop_a != 0:
				newList.append(pop_a)
			else:
				ans += f(newList)
				newList = []
		ans += f(newList)
		return ans
n = int(input())
a = list(map(int, input().split()))
print(f(a))


n = int(input())
h = list(map(int, input().split()))
cnt = 0
a = 0
for i in range(n - 1):
	if h[i + 1] < h[i]:
		cnt += h[i] - a
		a = h[i + 1]
cnt += h[-1] - a
print(cnt)


N = int(input())
h = list(map(int, input().split()))
result = 0
pre = 0
for x in h:
	result += max(x - pre, 0)
	pre = x
print(result)


n = int(input())
(*h,) = map(int, input().split())
import numpy as np
h = np.array(h)

def rec(hh):
	if len(hh) == 0:
		return 0
	if len(hh) == 1:
		return hh[0]
	i = np.argmin(hh)
	res = hh[i]
	l = rec(hh[:i] - hh[i])
	r = rec(hh[i + 1:] - hh[i])
	return res + l + r
print(rec(h))


n = int(input())
h = [0] + [int(i) for i in input().split()]
cnt = 0
for i in range(len(h) - 1):
	cnt += max(0, h[i + 1] - h[i])
print(cnt)


n = int(input())
array = [int(x) for x in input().split()]
now = 0
cnt = 0
for a in array:
	if a > now:
		cnt += a - now
	now = a
print(cnt)


n = int(input())
H = list(map(int, input().split()))
ans = 0
lst = 0
for h in H:
	if h > lst:
		ans += h - lst
	lst = h
print(ans)


input()
(ans, tmp) = (0, 0)
for h in map(int, input().split()):
	ans += max(0, h - tmp)
	tmp = h
print(ans)


n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
ans = 0
while a != b:
	ch = 0
	for i in range(n):
		if b[i] + 1 <= a[i]:
			b[i] += 1
			ch += 1
		elif b[i] + 1 > a[i] and ch > 0:
			ch = 0
			ans += 1
		if ch > 0 and i == n - 1:
			ans += 1
print(ans)


N = int(input())
H = [0] + [int(a) for a in input().split()]
a = 0
for i in range(1, N + 1):
	a += max(H[i] - H[i - 1], 0)
print(a)


n = int(input())
h = list(map(int, input().split()))
ans = 0
active = 0
for i in range(n):
	if active >= h[i]:
		active = h[i]
	else:
		ans += h[i] - active
		active = h[i]
print(ans)


from copy import deepcopy
n = int(input())
H = list(map(int, input().split()))
ans = 0
while any((h != 0 for h in H)):
	X = list()
	tmp = list()
	for h in H:
		if h != 0:
			X.append(h)
		else:
			if X:
				m = min(X)
				tmp += list([y - m for y in X])
				ans += m
				X = list()
			tmp += [0]
	if X:
		m = min(X)
		tmp += list([y - m for y in X])
		ans += m
		X = list()
	H = deepcopy(tmp)
print(ans)


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

def solve(heights, beg, end) -> int:
	if beg >= end:
		return 0
	try:
		idx = beg + heights[beg:end].index(0)
		return solve(heights, beg, idx) + solve(heights, idx + 1, end)
	except ValueError:
		pass
	minh = min(heights[beg:end])
	for i in range(beg, end):
		heights[i] -= minh
	return minh + solve(heights, beg, end)
cnt = solve(heights, 0, len(heights))
print(cnt)


N = int(input())
h = list(map(int, input().split()))
h.append(0)
pre = True
next = True
cnt = 0
for i in range(N):
	if h[i + 1] > h[i]:
		next = True
		if pre == False:
			cnt -= h[i]
	elif h[i + 1] < h[i]:
		next = False
		if pre == True:
			cnt += h[i]
	else:
		next = pre
	pre = next
print(cnt)


N = int(input())
h = list(map(int, input().split()))
h.insert(0, 0)
ans = 0
for i in range(N):
	ans += max(h[i + 1] - h[i], 0)
print(ans)


n = int(input())
h = list(map(int, input().split()))
tmp = [0 for i in range(n)]
ans = 0
right = 0
left = n - 1
while tmp != h:
	for i in range(n):
		if tmp[i] != h[i]:
			right = i
			left = i
			break
	for i in range(i + 1, n):
		if tmp[i] == h[i]:
			left = i - 1
			break
		elif i == n - 1 and tmp[n - 1] != h[n - 1]:
			left = n - 1
			break
	for i in range(right, left + 1):
		tmp[i] += 1
	ans += 1
print(ans)


(n, *h) = map(int, open(0).read().split())
print(sum((max(a - b, 0) for (a, b) in zip(h, h[1:] + [0]))))


(_, h) = open(0)
s = p = 0
for x in map(int, h.split()):
	s += max(x - p, 0)
	p = x
print(s)


def solve(N, hi):
	ans = 0
	for i in range(max(hi)):
		flg = False
		for n in range(N):
			if hi[n] != 0:
				if not flg:
					flg = True
					ans += 1
				hi[n] -= 1
			else:
				flg = False
	print(ans)

def __starting_point():
	N = int(input())
	hi = [int(i) for i in input().split()]
	solve(N, hi)
__starting_point()


n = int(input())
h = [0] + list(map(int, input().split())) + [0]
cnt = 0
while True:
	zero_ind = []
	for i in range(n + 2):
		if h[i] == 0:
			zero_ind.append(i)
	(start, end) = ([], [])
	for i in range(len(zero_ind) - 1):
		if zero_ind[i + 1] - zero_ind[i] > 1:
			start.append(zero_ind[i] + 1)
			end.append(zero_ind[i + 1])
	for (s, e) in zip(start, end):
		for i in range(s, e):
			h[i] -= 1
		cnt += 1
	if h.count(0) == n + 2:
		break
print(cnt)


def dfs(left, right):
	if right - left == 1:
		return h[left]
	elif right - left <= 0:
		return 0
	else:
		ret = min(h[left:right])
		k = 0
		for i in range(left, right):
			h[i] -= ret
			if h[i] == 0:
				k = i
		ret += dfs(left, k)
		ret += dfs(k + 1, right)
		return ret
N = int(input())
h = list(map(int, input().split()))
print(dfs(0, N))


import numpy as np
N = int(input().rstrip())
h = [int(i) for i in input().rstrip().split()]
check = [0] * N
height = [0] * N
count = 0
while True:
	check = [1 if h[i] == height[i] else 0 for i in range(N)]
	if check.count(1) == N:
		break
	count += 1
	for i in range(N):
		if check[i] == 0:
			height[i] += 1
			if i < N - 1 and check[i + 1] == 1:
				break
print(count)


n = int(input())
h = list(map(int, input().split()))
l = [h[i + 1] - h[i] for i in range(n - 1) if h[i + 1] - h[i] > 0]
print(sum(l) + h[0])


N = int(input())
H = list(map(int, input().split()))
V = sum(H)
E = 0
for i in range(1, N):
	E += min(H[i - 1], H[i])
print(V - E)


a = int(input())
A = list(map(int, input().split())) + [0]
s = 0
m = 0
for i in A:
	s += abs(m - i)
	m = i
print(s // 2)


n = int(input())
h = [0] + list(map(int, input().split())) + [0]
ma = 0
mi = float('inf')
ans = 0
for i in range(n + 1):
	if h[i] <= h[i + 1]:
		ma = max(ma, h[i + 1])
		mi = min(mi, h[i])
	else:
		ans += ma - mi
		ma = h[i + 1]
		mi = h[i + 1]
print(ans)


n = int(input())
pre = 0
ans = 0
for i in map(int, input().split()):
	if i < pre:
		ans += pre - i
	pre = i
else:
	print(ans + i)


N = int(input())
hs = map(int, input().split())
b = 0
m = 0
for h in hs:
	if b > h:
		m += b - h
	b = h
m += b
print(m)


input()
h = [0]
h.extend([int(i) for i in input().split()])
ans = 0
for i in range(len(h) - 1):
	ans += max(h[i + 1] - h[i], 0)
print(ans)


n = int(input())
l = [0] + list(map(int, input().split()))
a = 0
for i in range(n):
	a += max(l[i + 1] - l[i], 0)
print(a)


n = int(input())
h = list(map(int, input().split()))
cnt = 0
grow = True
while grow:
	inc = False
	grow = False
	for i in range(n):
		if h[i] == 0:
			inc = False
		else:
			h[i] -= 1
			if not inc:
				inc = True
				grow = True
				cnt += 1
print(cnt)


n = int(input())
h = list(map(int, input().split()))
hmax = max(h)
ans = 0
f = False
for i in range(1, hmax + 1):
	for j in range(n):
		if f and h[j] < i:
			ans += 1
		f = h[j] >= i
	if f:
		ans += 1
	f = False
print(ans)


N = int(input())
H = list(map(int, input().split()))
ans = 0
a = 0
for i in H:
	ans += max(i - a, 0)
	a = i
print(ans)


n = int(input())
h = list(map(int, input().split()))
cnt = 0
for i in range(n - 1):
	cnt += min(h[i], h[i + 1])
print(sum(h) - cnt)


n = int(input())
H = [0] + list(map(int, input().split())) + [0]
ans = sum([max(0, j - i) for (i, j) in zip(H, H[1:])])
print(ans)


N = int(input())
H = list(map(int, input().split()))
H.append(0)
cnt = 0
for i in range(N + 1):
	cnt += max(H[i] - H[i - 1], 0)
print(cnt)


(n, *h) = map(int, open(0).read().split())
a = h[0]
for i in range(1, n):
	if h[i - 1] < h[i]:
		a += h[i] - h[i - 1]
print(a)


input()
h = list(map(int, input().split()))
print(sum((max(0, h[i + 1] - h[i]) for i in range(len(h) - 1))) + h[0])


n = int(input())
a = 0
ans = 0
for b in map(int, input().split()):
	if b >= a:
		ans += b - a
	a = b
print(ans)


n = int(input())
h = list(map(int, input().split()))
c = h[0]
for i in range(n - 1):
	x = h[i + 1] - h[i]
	if x > 0:
		c += x
print(c)


n = int(input())
h = list(map(int, input().split()))
s = 0
for i in range(max(h) + 1):
	flag = False
	for j in range(n):
		if flag and h[j] == 0:
			s += 1
			flag = False
		elif not flag and h[j] > 0:
			flag = True
		h[j] = max(h[j] - 1, 0)
	if flag:
		s += 1
print(s)


N = int(input())
ans = 0
tmp = 0
for x in list(map(int, input().split())):
	ans += max(0, x - tmp)
	tmp = x
print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, *H) = list(map(int, read().split()))
	ans = 0
	while True:
		changed = changed2 = False
		for i in range(N):
			if H[i] > 0:
				H[i] -= 1
				changed = True
				changed2 = True
			elif changed:
				ans += 1
				changed = False
		if changed:
			ans += 1
		if not changed2:
			break
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


N = int(input())
(*H,) = map(int, input().split())
L = len(H)
ans = 0
active = 0
for i in range(N):
	if H[i] <= active:
		active = H[i]
	else:
		ans += H[i] - active
		active = H[i]
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(max(a)):
	cnt = 1 if a[0] - i >= 1 else 0
	for j in range(1, n):
		if a[j - 1] - i < 1 and a[j] - i >= 1:
			cnt += 1
	ans += cnt
print(ans)


n = int(input())
h = [0] + list(map(int, input().split()))
(ans, temp) = (0, -1)
while True:
	for i in range(n + 1):
		if temp == 0 and h[i] != 0:
			ans += 1
		temp = h[i]
		h[i] = max(h[i] - 1, 0)
	if all((v == 0 for v in h)):
		break
print(ans)


def solve(L):
	if not L:
		return 0
	if 0 not in L:
		return min(L) + solve([l - min(L) for l in L])
	tmp = 0
	(l, p) = (0, False)
	for i in range(len(L)):
		if L[i] == 0:
			if p:
				p = False
				tmp += solve(L[l:i])
				l = i + 1
			else:
				l = i + 1
		elif not p:
			p = True
	return tmp + solve(L[l:])
N = int(input())
H = list(map(int, input().split()))
print(solve(H))


n = int(input())
H = list(map(int, input().split()))
cnt = H[0]
for i in range(1, n):
	cnt += max(H[i] - H[i - 1], 0)
print(cnt)


n = int(input())
h = list(map(int, input().split()))
ans = 0
pos = 0
for i in h:
	ans += max(i - pos, 0)
	pos = i
print(ans)


N = int(input())
(*H,) = map(int, input().split())
L = len(H)
cnt = 0
prv = 0
for i in range(N):
	if prv < H[i]:
		cnt += H[i] - prv
	prv = H[i]
print(cnt)


n = int(input())
h = list(map(int, input().split()))
h.append(0)
count = 0
while h != [0] * (n + 1):
	for i in range(len(h)):
		if h[i] != 0:
			break
	for j in range(i, len(h) + 1):
		if h[j] == 0:
			break
	for x in range(i, j):
		h[x] -= 1
	count += 1
print(count)


n = int(input())
a = list(map(int, input().split()))
res = a[-1]
for i in range(n - 1):
	if a[i + 1] < a[i]:
		res += a[i] - a[i + 1]
print(res)


N = int(input())
count = 0
p = 0
for h in map(int, input().split()):
	count += max(0, h - p)
	p = h
print(count)


n = int(input())
cnt = 0
thre = 0
for h in (int(h) for h in input().split()):
	cnt += h - thre if h > thre else 0
	thre = h
print(cnt)


N = int(input())
h = [int(x) for x in input().split()]
ans = sum(h)
for i in range(0, N - 1):
	ans -= min(h[i + 1], h[i])
print(ans)


import bisect, collections, copy, itertools, math, string
import sys

def I():
	return int(sys.stdin.readline().rstrip())

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

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip.split())

def main():
	n = I()
	h = LI()
	ok = 0
	ng = 0
	ans = 0
	for (i, x) in enumerate(h):
		if x > 0:
			ok = i
			break
	else:
		ok = n
	while ok != n:
		for (i, x) in enumerate(h[ok + 1:]):
			if x == 0:
				ng = ok + 1 + i
				break
		else:
			ng = n
		sub = [0] * ok + [1] * (ng - ok) + [0] * (n - ng)
		for i in range(n):
			h[i] -= sub[i]
		for (i, x) in enumerate(h):
			if x > 0:
				ok = i
				break
			else:
				ok = n
		ans += 1
	print(ans)
main()


n = int(input())
h = list(map(int, input().split()))
result = 0
while True:
	if max(h) == 0:
		break
	i = 0
	while i < n:
		if h[i] <= 0:
			i += 1
		else:
			result += 1
			while i < n and h[i] > 0:
				h[i] -= 1
				i += 1
print(result)


(n, a) = open(0)
l = a.split()
print(sum((max(int(j) - int(i), 0) for (i, j) in zip(['0'] + l, l))))


import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque, Counter
from decimal import Decimal
import functools

def v():
	return input()

def k():
	return int(input())

def S():
	return input().split()

def I():
	return map(int, input().split())

def X():
	return list(input())

def L():
	return list(input().split())

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

def lcm(a, b):
	return a * b // math.gcd(a, b)
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7
cnt = 0
ans = 0
inf = float('inf')
n = k()
h = l()
for i in range(1, n):
	if h[i - 1] - h[i] > 0:
		ans += h[i - 1] - h[i]
print(ans + h[-1])


n = int(input())
h = list(map(int, input().split()))
cnt = 0
for hh in range(1, max(h) + 1):
	flg = False
	for i in range(n):
		if h[i] >= hh:
			flg = True
		elif flg:
			flg = False
			cnt += 1
	if flg:
		flg = False
		cnt += 1
print(cnt)


input()
H = list(map(int, input().split()))
ans = 0
for i in range(len(H) - 1):
	if H[i + 1] < H[i]:
		ans += H[i] - H[i + 1]
print(ans + H[-1])


(n, *a) = map(int, open(0).read().split())
ans = 0
pre = 0
for i in a:
	if i > pre:
		ans += i - pre
	pre = i
print(ans)


N = int(input())
a = list(map(int, input().split()))
s = a[0]
for i in range(N - 1):
	s += max(a[i + 1] - a[i], 0)
print(s)


n = int(input())
h = list(map(int, input().split()))
a = 0
c = 0
for i in range(n):
	if c < h[i]:
		a += h[i] - c
	c = h[i]
print(a)


N = int(input())
A = list(map(int, input().split())) + [0]
cnt = 0
for i in range(N):
	if A[i] > A[i + 1]:
		cnt += A[i] - A[i + 1]
print(cnt)


N = int(input())
h = [int(i) for i in input().split()]
count = h[0]
for i in range(1, N):
	if h[i] > h[i - 1]:
		count += h[i] - h[i - 1]
print(count)


N = int(input())
hs = [0] + input().split()
cnt = 0
for i in range(1, len(hs)):
	cnt += max(int(hs[i]) - int(hs[i - 1]), 0)
print(cnt)


n = int(input())
h = list(map(int, input().split()))
h.append(101)
ans = 0
start = 0
i = 0
while sum(h[:n]) != 0:
	if h[i] != 0:
		h[i] -= 1
	if h[i] == 0:
		start = i + 1
	if h[i] >= h[i + 1] or i == n - 1:
		ans += 1
		i = start
		continue
	i += 1
print(ans)


(n, *l) = map(int, open(0).read().split())
count = l[0]
for i in range(1, n):
	if l[i - 1] < l[i]:
		count += l[i] - l[i - 1]
print(count)


a = int(input())
b = input().split()
p = 0
n = 0
for i in b:
	i = int(i)
	if i > p:
		n += i - p
	p = i
print(n)


n = int(input())
h = list(map(int, input().split()))
flag = False
ans = 0
while not flag:
	for i in range(n):
		if flag:
			if h[i] != 0:
				h[i] -= 1
			else:
				break
		elif not flag and h[i] != 0:
			flag = True
			h[i] -= 1
			ans += 1
	if not flag:
		break
	flag = False
print(ans)


def readinput():
	n = int(input())
	h = list(map(int, input().split()))
	return (n, h)

def main(n, h):
	count = 0
	hmax = max(h)
	for i in range(hmax):
		j = 0
		mizuyari = False
		for j in range(n):
			if h[j] > 0:
				if mizuyari == False:
					mizuyari = True
					count += 1
				h[j] -= 1
			else:
				mizuyari = False
	return count

def __starting_point():
	(n, h) = readinput()
	ans = main(n, h)
	print(ans)
__starting_point()


N = int(input())
h = list(map(int, input().split()))
print(sum((max(0, h[x] - h[x + 1]) for x in range(N - 1))) + h[-1])


def divide_and_conuer(ls):
	mi = ls.index(min(ls))
	res = ls[mi]
	if ls[mi + 1:len(ls)] != list():
		res += divide_and_conuer(ls[mi + 1:len(ls)]) - ls[mi]
	if ls[0:mi] != list():
		res += divide_and_conuer(ls[0:mi]) - ls[mi]
	return res

def main():
	n = int(input())
	a = list(map(int, input().split()))
	print(divide_and_conuer(a))

def __starting_point():
	main()
__starting_point()


(N,) = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
r = h[0]
for i in range(1, N):
	r += max(0, h[i] - h[i - 1])
print(r)


n = int(input())
h = list(map(int, input().split(' ')))
cnt = 0
minNum = 0
tmp = 0
while True:
	for i in range(h.count(0)):
		if h.index(0) == 0:
			h.pop(0)
		elif h.index(0) > 0:
			tmp = h.index(0)
			break
	else:
		tmp = len(h)
	if not h:
		break
	if tmp == 1:
		cnt += h[0]
		h.pop(0)
	else:
		minNum = min(h[0:tmp])
		cnt += minNum
		for j in range(tmp):
			h[j] -= minNum
print(cnt)


N = int(input())
H = list(map(int, input().split()))
active = 0
ans = 0
for i in range(N):
	if H[i] >= active:
		ans += H[i] - active
		active = H[i]
	else:
		active = H[i]
print(ans)


n = int(input())
h = [int(i) for i in input().split()]
c = 0
cur = 0
for i in h:
	if cur < i:
		c += i - cur
	cur = i
print(c)


from sys import stdin
from numpy import argmin
n = int(stdin.readline().strip())
h_lst = [int(x) for x in stdin.readline().split()]
cnt = 0

def glow(lst, start_pos):
	nonlocal cnt
	if len(lst) == 0:
		return -1
	elif len(lst) == 1:
		cnt += lst[0] - start_pos
		return -1
	else:
		pos = min(lst)
		cnt += pos - start_pos
		id_ = argmin(lst)
		glow(lst[:id_], pos)
		glow(lst[id_ + 1:], pos)
glow(h_lst, 0)
print(cnt)


def inpl():
	return [int(i) for i in input().split()]
N = int(input())
H = [0] + inpl()
print(sum([max(0, H[i + 1] - H[i]) for i in range(N)]))


N = int(input())
h = [int(n) for n in input().split()]
print(sum([h[i] - h[i + 1] for i in range(N - 1) if h[i] > h[i + 1]], h[-1]))


N = int(input())
h = [int(i) for i in input().split()]
ans = 0
count = 0
while h != [0] * N:
	f = False
	count = 0
	for i in range(N):
		if h[i] != 0 and f == False:
			f = True
			count += 1
		if h[i] == 0 and f == True:
			f = False
	ans += count
	for i in range(N):
		h[i] = max(h[i] - 1, 0)
print(ans)


n = int(input())
al = list(map(int, input().split()))
res = 0
temp = 0
for i in range(n):
	if al[i] >= temp:
		res += al[i] - temp
		temp = al[i]
	else:
		temp = al[i]
print(res)


(N, *h) = map(int, open(0).read().split())
ans = sum([max(h[i + 1] - h[i], 0) for i in range(N - 1)])
print(ans + h[0])


n = int(input())
l = list(map(int, input().split()))
now = 0
ans = 0
for x in l:
	if x > now:
		ans += x - now
	now = x
print(ans)


n = int(input())
hs = list(map(int, input().split()))
ans = hs[-1]
for i in range(1, n):
	if hs[i] < hs[i - 1]:
		ans += hs[i - 1] - hs[i]
	else:
		continue
print(ans)


N = int(input())
h = list(map(int, input().split()))
max_ = 100 * 50
h = [0] + h + [0]
cnt = 0
if max(h) == 0:
	print(0)
	return
for _ in range(max_):
	for i in range(1, N + 1):
		if h[i] == 0 and h[i - 1] != 0:
			cnt += 1
			break
		if h[i] > 0:
			h[i] -= 1
			if h[i] == 0 and h[i + 1] == 0:
				cnt += 1
				break
		if i == N:
			cnt += 1
			break
	if sum(h) == 0:
		break
print(cnt)


n = int(input())
(*L,) = map(int, input().split())
w = 0
b = 0
for i in L:
	if i > b:
		w += i - b
	b = i
print(w)


N = int(input())
H = [int(x) for x in input().split()]
ans = 0
for i in range(max(H)):
	count = 0
	flag = False
	for j in range(N):
		if i < H[j]:
			if flag == False:
				count += 1
			flag = True
		else:
			flag = False
	ans += count
print(ans)


N = int(input())
h = list(map(int, input().split()))
s = 0
while h != [0] * N:
	c = 0
	for i in range(N - 1):
		if h[i] != 0 and h[i + 1] == 0:
			c += 1
	if h[N - 1] != 0:
		c += 1
	for i in range(N):
		if h[i] != 0:
			h[i] -= 1
	s += c
print(s)


(N, *H) = map(int, open(0).read().split())
cnt = 0
prv = 0
for h in H:
	cnt += max(0, h - prv)
	prv = h
print(cnt)


n = int(input())
h = list(map(int, input().split()))
ans = 0

def solve(li_h):
	l = 0
	for i in li_h:
		if i == 0:
			l += 1
		else:
			break
	r = l + 1
	for i in li_h[l + 1:]:
		if i == 0:
			break
		r += 1
	for i in range(l, r):
		li_h[i] -= 1
	return li_h
while sum(h) != 0:
	h = solve(h)
	ans += 1
print(ans)


n = int(input())
h = list(map(int, input().split()))
ans = 0
tmp = 0
for x in h:
	if tmp < x:
		ans += x - tmp
	tmp = x
print(ans)