Найдите, какое минимальное число фигурок ей понадобится, чтобы Мила смогла заполнить нижние ряды поля, образовав прямоуг

#import sys
 
#sys.stdin = open('input.txt', 'r')
n = int(input())
a = list(map(int, input().split()))
#sys.stdin.close()
 
ans = 0
heights_stack = [0]
height_max = max(a)
a.append(height_max)
 
for i in range(n + 1):
    hole_height = height_max - a[i]
    while hole_height < heights_stack[-1]:
        ans += heights_stack.pop() - heights_stack[-1]
    if hole_height > heights_stack[-1]:
        heights_stack.append(hole_height)
 
#sys.stdout = open('output.txt', 'w')
print(ans)
#sys.stdout.close()

n = int(input())
ll = list(map(int, input().split()))
prover=False
k=0
if max(ll)!=min(ll):
    while min(ll)>0:
        for i in range(0, n):
            ll[i]-=1
    for el in ll:
        if el==0 and not prover:
            prover=True
            k+=1
        elif el!=0 and prover:
            prover=False
    while max(ll)!=0:
        for i in range(0, n):
            if ll[i] == 0:
                ll[i] += 1
        for i in range(0, n):
            ll[i] -= 1
        if max(ll)!=0:
            for el in ll:
                if el == 0 and not prover:
                    prover = True
                    k += 1
                elif el != 0 and prover:
                    prover = False
print(k)

num = [1,3,4,4,5,6,1,6,1,1]
num = [9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,1]
k = 0
mnum = max(num)
while len(num) > 1 :
    tmp = [num[0]]
    for i in range(1, len(num)) :
        if num[i] != num [i - 1] :
            tmp.append(num[i])
    num = tmp.copy()
    ind = num.index(min(num))
    a = num[ind - 1] if ind else mnum
    b = num[ind + 1] if ind < len(num) - 1 else mnum
    k += min(a,b) - num[ind]
    del num[ind]
print(k)

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

#import sys
 
#sys.stdin = open('input.txt', 'r')
n = int(input())
a = list(map(int, input().split()))
#sys.stdin.close()
 
ans = 0
heights_stack = [0]
height_max = max(a)
a.append(height_max)
 
for i in range(n + 1):
    hole_height = height_max - a[i]
    while hole_height < heights_stack[-1]:
        popped = heights_stack.pop()
        next_height = heights_stack[-1]
        if next_height < hole_height:
            next_height = hole_height
        ans += popped - next_height
        
    if hole_height > heights_stack[-1]:
        heights_stack.append(hole_height)
 
#sys.stdout = open('output.txt', 'w')
print(ans)
#sys.stdout.close()

n = int(input())
a = list(map(int, input().split()))
#В переменной ans будем накапливать
#результат - суммарное количество
#блоков. Пока что сумма равна 0.
ans = 0
#В стек сразу кладем число 0. Это
#число никогда не будет извлекаться
#из стека, поскольку высота дыр
#в алгоритме >= 0. Значит, в стеке
#всегда будет как минимум 1 элемент
#и обращение к последнему элементу
#стека всегда будет безопасным.
heights_stack = [0]
#Находим максимальную высоту столбика
#в стакане.
height_max = max(a)
#Добавляем в стакан еще один столбик
#с максимальной высотой
#(распоследний), чтобы гарантировать,
#что после последнего столбика будет
#еще распоследний, и алгоритм
#опустошит стек полностью после
#обработки всех столбцов.
#Альтернатива - дополнительная
#проверка состояния стека после
#окончания алгоритма и его
#опустошение при необходимости.
#Но так короче.
a.append(height_max)
#Верхняя граница цикла не n, а n + 1,
#потому что мы добавили распоследний
#столбец.
for i in range(n + 1):
    #Находим высоту (или глубину? как
    #правильнее сказать?) дыры,
    #которую необходимо заполнить,
    #чтобы высота столбика стала
    #равной высоте самого высокого
    #столбика в стакане.
    hole_height = height_max - a[i]
    #Если мы видим, что дыры слева от
    #текущей по высоте (глубине)
    #превышают высоту текущей дыры,
    #то понимаем, что пора их
    #заполнить блоками, потому что
    #они уже все, ограничены
    #столбиками и слева, и справа.
    while hole_height < heights_stack[-1]:
        #Извлекли информацию о
        #глубине, на которую можно
        #погрузить очередной блок
        #слева.
        popped = heights_stack.pop()
        #Извлекли информацию о
        #следующей доступной глубине.
        next_height = heights_stack[-1]
        #Если следующая доступная
        #глубина меньше высоты
        #текущей дыры, то она
        #полностью ограничена
        #столбиком только слева, а
        #справа лишь частично,
        #поэтому заполняем ее только
        #до высоты текущей дыры.
        if next_height < hole_height:
            next_height = hole_height
        #Подсчитали количество блоков,
        #потраченных на заполнение
        #дыр слева, и добавили
        #к ответу.
        ans += popped - next_height
    #Если нашли дыру более высокую
    #(глубокую), чем текущая, то
    #нашли и еще один ограничивающий
    #наши дыры столбик слева.
    #Запоминаем информацию в стеке
    #для будущего использования.
    if hole_height > heights_stack[-1]:
        heights_stack.append(hole_height)
#В конце цикла натыкаемся на
#распоследний столбец, который имеет
#максимальную высоту и гарантированно
#ограничивает все дыры справа. Самое
#время заполнить все оставишеся дыры...
#...и вывести результат.
print(ans)