28523번 - Инопланетные кальмары 다국어

Во время очередного путешествия Рик столкнулся с толпами инопланетных кальмаров. Кальмары достаточно умны, поэтому, нападая на кого-нибудь, обязательно выстраиваются в колонны, образуя гистограмму (набор столбцов с общей нижней границей). Например, колонны размеров $1$, $3$, $4$ и $2$ можно представить в виде:

  x 
 xx 
 xxx
xxxx

Чтобы вернуться как можно скорее домой, Рик решил переместить их в другую вселенную. Для этого наш герой изобрел лазерный телепортер. Для использования этого прибора нужно выбрать несколько подряд идущих колонн одинаковой высоты $h$ и число $0 < x \leqslant h$, то есть такое, что в каждой из выбранных колонн есть хотя бы $x$ кальмаров. Тогда после использования телепортера первые $x$ кальмаров в каждой из выбранных колонн перемещаются в другую вселенную (а высоты каждой из выбранных коллонн уменьшаются на $x$).

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

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

В первой строке вводится одно единственное число $n$ --- количество колонн из кальмаров ($1 \leqslant n \leqslant 2 \cdot 10^5$).

В следующей строке дано $n$ целых чисел $a_i$ --- количество кальмаров в каждой колонне ($0 \leqslant a_i \leqslant 10^9$).

Выведите одно единственное число --- ответ на задачу.