C. Помогаем природе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Леон живет в лесу. Недавно он заметил, что некоторые деревья возле его любимой тропинки засыхают, а другие наоборот слишком увлажнены. Леон очень любит свой лес, поэтому решил научиться контролировать уровень влажности почвы, чтобы спасти деревья.

Возле тропинки растут $$$n$$$ деревьев, текущие уровни влажности которых заданы массивом $$$a_1, a_2, \dots, a_n$$$. Леон научился трем способностям, которые помогут ему осушать и поливать почву.

  • Он может выбрать позицию $$$i$$$ и уменьшить уровень влажности деревьев $$$1, 2, \dots, i$$$ на $$$1$$$.
  • Он может выбрать позицию $$$i$$$ и уменьшить уровень влажности деревьев $$$i, i + 1, \dots, n$$$ на $$$1$$$.
  • Увеличить уровень влажности всех деревьев на $$$1$$$.

Леон хочет узнать минимальное число действий, которое необходимо совершить, чтобы каждое дерево имело уровень влажности равный $$$0$$$.

Входные данные

В первой строке вводится одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).

Во второй строке вводятся $$$n$$$ целых чисел $$$a_1, a_2 \ldots a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — изначальные уровни влажности деревьев.

Выходные данные

Выведите одно целое число — минимальное число действий.

Система оценки

В данной задаче 25 тестов, помимо тестов из условия, каждый из них оценивается в 4 балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие на упорядоченном по неубыванию массиве, наберут не менее $$$28$$$ баллов.

Решения, корректно работающие на массивах, которые до некоторой позиции убывают, а после нее возрастают, наберут не менее $$$44$$$ баллов.

Решения, корректно работающие на массиве с не более, чем одним не нулем, наберут не менее $$$16$$$ баллов.

Примеры
Входные данные
3
-2 -2 -2
Выходные данные
2
Входные данные
3
10 4 7
Выходные данные
13
Примечание

В первом примере из условия достаточно $$$2$$$ раза применить операцию прибавления $$$1$$$ ко всему массиву.

Во втором примере из условия можно $$$4$$$ раза применить операцию вычитания на префиксе длины $$$3$$$ и получить массив $$$6, 0, 3$$$.

После этого $$$6$$$ раз применить операцию вычитания на префиксе длины $$$1$$$ и $$$3$$$ раза операцию вычитания на суффиксе длины $$$1$$$. Итого, количество действий составит $$$4 + 6 + 3 = 13$$$. Можно показать, что меньшим количеством действий обойтись нельзя, поэтому $$$13$$$ — это ответ.