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