Олимпиадный тренинг

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


Игра 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
 
Замечание
Пример соответствует рисунку. Черным цветом обозначен камень, серым  вода.


time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w6423
Python26
Комментарий учителя