Маленький Леон живет в лесу. Недавно он заметил, что некоторые деревья возле его любимой тропинки засыхают, а другие наоборот слишком увлажнены. Леон очень любит свой лес, поэтому решил научиться контролировать уровень влажности почвы, чтобы спасти деревья.
Возле тропинки растут \(n\) деревьев, текущие уровни влажности которых заданы массивом \(a_1, a_2, \dots, a_n\). Леон научился трем способностям, которые помогут ему осушать и поливать почву.
- Выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(1, 2, \dots, i\) на \(1\).
- Выбрать позицию \(i\) и уменьшить уровень влажности деревьев \(i, i + 1, \dots, n\) на \(1\).
- Увеличить уровень влажности всех деревьев на \(1\).
Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный \(0\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное число действий. Можно показать, что ответ всегда существует.
Примечание
В первом наборе входных данных достаточно \(2\) раза применить операцию прибавления \(1\) ко всему массиву.
Во втором наборе входных данных можно \(4\) раза применить операцию вычитания на префиксе длины \(3\) и получить массив \(6, 0, 3\).
После этого \(6\) раз применить операцию вычитания на префиксе длины \(1\) и \(3\) раза операцию вычитания на суффиксе длины \(1\). Итого, количество действий составит \(4 + 6 + 3 = 13\). Можно показать, что меньшим количеством действий обойтись нельзя, поэтому \(13\) — это ответ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5
|
2
13
36
33
|