Задача №115129. Помогаем природе
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Маленький Леон живет в лесу. Недавно он заметил, что некоторые деревья возле его любимой тропинки засыхают, а другие наоборот слишком увлажнены. Леон очень любит свой лес, поэтому решил научиться контролировать уровень влажности почвы, чтобы спасти деревья.
Возле тропинки растут \(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\)) — изначальные уровни влажности деревьев.
Выведите одно целое число — минимальное число действий.
В первом примере из условия достаточно \(2\) раза применить операцию прибавления \(1\) ко всему массиву.
Во втором примере из условия можно \(4\) раза применить операцию вычитания на префиксе длины \(3\) и получить массив \(6, 0, 3\).
После этого \(6\) раз применить операцию вычитания на префиксе длины \(1\) и \(3\) раза операцию вычитания на суффиксе длины \(1\). Итого, количество действий составит \(4 + 6 + 3 = 13\). Можно показать, что меньшим количеством действий обойтись нельзя, поэтому \(13\) — это ответ.
В данной задаче 25 тестов, помимо тестов из условия, каждый из них оценивается в 4 балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие на упорядоченном по неубыванию массиве, наберут не менее \(28\) баллов.
Решения, корректно работающие на массивах, которые до некоторой позиции убывают, а после нее возрастают, наберут не менее \(44\) баллов.
Решения, корректно работающие на массиве с не более, чем одним не нулем, наберут не менее \(16\) баллов.
3 -2 -2 -2
2
3 10 4 7
13