Омкар строит водную горку в своем аквапарке, и ему нужна ваша помощь, чтобы сделать это как можно эффективнее.
В настоящее время у Омкара есть \(n\) опор, выстроенных в линию, \(i\)-я из которых имеет высоту \(a_i\). Омкар хочет построить свою водную горку справа налево, поэтому его опоры должны быть неспадающими по высоте, чтобы выдержать водную горку. За \(1\) операцию Омкар может сделать следующее: взять любой последовательный подотрезок опор, неспадающий по высотам, и добавить \(1\) к высоте каждой из них.
Помогите Омкару найти минимальное количество операций, которые ему нужно сделать, чтобы его опоры смогли выдержать его водную горку!
Последовательность \(b\) является подотрезком \(c\), если \(b\) может быть получена из \(c\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Массив \(b_1, b_2, \dots, b_n\) называется неспадающим, если \(b_i\le b_{i+1}\) для каждого \(i\) от \(1\) до \(n-1\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, которое необходимо выполнить Омкару, чтобы его опоры могли выдерживать его водную горку.
Примечание
Подмассив, с которым Омкар выполняет операцию, выделен жирным шрифтом.
В первом наборе входных данных:
Первая операция:
\([5, 3, \textbf{2}, 5] \to [5, 3, \textbf{3}, 5]\)
Вторая операция:
\([5, \textbf{3}, \textbf{3}, 5] \to [5, \textbf{4}, \textbf{4}, 5]\)
Третья операция:
\([5, \textbf{4}, \textbf{4}, 5] \to [5, \textbf{5}, \textbf{5}, 5]\)
В третьем наборе входных данных массив уже является неспадающим, поэтому Омкар выполняет \(0\) операций.