Описание

Ограничение по времени: 1000 ms
Ограничение по памяти: 256 Mb

Ответы на вопросы

Задача: Двумерный дождь

Игра PitCraft происходит в двумерном мире, который состоит из блоков размером 1 на 1 метр.
Остров игрока представляет собой набор столбцов различной высоты, состоящих из блоков камня и окруженный морем.
Над островом прошёл сильный дождь, который заполнил водой все низины, а не поместившаяся в них вода стекла в море, не увеличив его уровень. По ландшафту острова определите, сколько блоков воды осталось после дождя в низинах на острове.
 
Формат входных данных
В первой строке записано натуральное число N (0 <= N <= 100 000)  количество столбцов, задающих ландшафт острова.
Во второй строке записано N натуральных чисел Hi (1 <= Hi <= 109)  высоты столбцов.
 
Формат выходных данных
Выведите одно число  количество блоков занятых водой.
Система оценки
Решения, верно работающие при N <= 100, будут набирать не менее половины баллов.

Ввод Вывод
11
2 5 2 3 6 9 3 1 3 4 6
18


Замечание
Пример соответствует рисунку. Черным цветом обозначен камень, серым  вода.



Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: