Известный город

Очень простая

Ограничение по времени выполнения 3 секунды

Ограничение по использованию памяти 32 мегабайта

После прибытия в Варшаву, мистер Б был поражен небоскребами и сделал несколько фотографий. Однако, рассматривая эти фотографии, он с удивлением обнаружил, что не может определить количество зданий на них. Поэтому он решил поступить следующим образом:

Разделить фотографию на ( n ) вертикальных частей, начиная слева направо. Здания на фотографии можно представить в виде прямоугольников, нижний край которых совпадает с горизонтом. Одно здание может занимать несколько последовательных частей, но каждая часть может содержать только одно видимое здание или не содержать зданий вовсе.
Измерить высоту каждого здания в каждой части.
Написать программу, которая вычислит минимальное количество зданий.

Мистер Б завершил первые два шага, теперь ваша очередь выполнить последний.

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

Каждый тестовый случай начинается со строки, содержащей целое число ( n ) (( 1 $\leq$ n $\leq$ 100000 )). Далее следует строка, содержащая ( n ) целых чисел, представляющих высоту здания в каждой части. Обратите внимание, что нулевая высота означает отсутствие здания в этой части. Все входные числа неотрицательны и меньше ( 1000000000 ).

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

Для каждого тестового случая выведите одну строку, содержащую номер случая и минимально возможное количество зданий на фотографии.

Примеры

Ввод #1

Ответ #1

Примечание

Возможные конфигурации примеров иллюстрированы ниже:

Отправки 139

Коэффициент принятия 40 %