Маленький Слоник любит сортировки.
У него есть массив a из n целых чисел. Пусть элементы массива пронумерованы от 1 до n, тогда элемент номер i обозначим ai. За один шаг Маленький Слоник может выбрать произвольную пару целых чисел l и r (1 ≤ l ≤ r ≤ n) и увеличить ai на 1 для всех i таких, что l ≤ i ≤ r.
Помогите Маленькому Слонику найти минимальное количество шагов, за которое он может преобразовать массив a в произвольный отсортированный по неубыванию массив. Массив a, состоящий из n элементов, отсортирован по неубыванию, если для любого i (1 ≤ i < n) выполняется ai ≤ ai + 1.
Выходные данные
В единственной строке выведите единственное целое число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере массив уже отсортирован по неубыванию, поэтому ответ 0.
Во втором примере нужно использовать две операции: первый раз увеличить числа от второго до третьего (после этого массив станет следующим: [3, 3, 2]), а второй раз увеличить только последний элемент (массив станет: [3, 3, 3]).
В третьем примере нужно использовать как минимум 6 шагов. Возможная последовательность операций: (2; 3), (2; 3), (2; 3), (3; 3), (3; 3), (3; 3). После этого массив преобразуется в [7, 7, 7, 47].
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
|
0
|
|
2
|
3
3 2 1
|
2
|
|
3
|
4
7 4 1 47
|
6
|