Відоме місто#3588
Після прибуття до Варшави, пан Б був вражений хмарочосами і зробив кілька фотографій. Проте, переглядаючи їх, він зрозумів, що не може визначити кількість будівель на знімках. Щоб вирішити цю проблему, він вирішив діяти так:
розділити фотографію на вертикальних частин зліва направо. Будівлі на фото можна уявити як прямокутники, нижній край яких лежить на горизонті. Одна будівля може займати кілька послідовних частин, але кожна частина може містити лише одну видиму будівлю або не містити жодної.
виміряти висоту будівлі в кожній частині.
написати програму, яка обчислить мінімальну кількість будівель.
Пан Б вже виконав перші два кроки, тепер ваша черга завершити останній.
Кожен тестовий випадок починається з рядка, що містить ціле число (1 \leq n \leq 100\,000). Далі йде рядок з цілих чисел, що представляють висоту будівлі в кожній частині. Зверніть увагу, що нульова висота означає відсутність будівлі в цій частині. Усі вхідні числа є невід'ємними і меншими за 1\,000\,000\,000.
Для кожного тестового випадку виведіть один рядок, що містить номер випадку та мінімально можливу кількість будівель на фото.
Приклад 1
Можливі конфігурації зразків ілюстровані нижче:
