Задачі
Укладування плит
Укладування плит
Відомий програміст Петрик знову взявся за написання нової комп'ютерної гри у стилі платформер. На одному з рівнев у нього є коридор, розбитий на \textbf{N} рівних ділянок. Цей коридор повинен бути покрий плитами. Одна плита може мати довільну довжину і відповідно покривати декілька послідовних ділянок. Потрібно виконати укладування плит таким чином, щоб кожну ділянку було покрито заданою кількістю плит. Допоможіть Петрику порахувати мінімальну кількість плит, яка йомо знадобиться для цього.
\InputFile
У першому рядку задано ціле число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{200000}) -- довжина коридору. у другому рядку записано \textbf{N} цілих чисел, кожне з яких визначає кількість плит, якими повинна бути покрита відповідна ділянка. Всі числа невід'ємні і не перевищують \textbf{10^9}.
\OutputFile
Виведіть мінімальну кількість плит, яка потрібна для укладки.
Вхідні дані #1
3 3 4 1
Вихідні дані #1
4