Аркадий решил пронаблюдать за рекой в течение n последовательных дней. Уровень воды в реке в каждый из этих дней равен некоторому вещественному значению.
Аркадий каждый день ходит к реке и делает отметку текущего уровня воды на берегу. Если отметка существует до этого, новая отметка не создается. Вода не смывает отметки. Аркадий выписал, сколько отметок было строго над уровнем воды в каждый из дней, в i-й день это количество равнялось mi.
Определим di как количество отметок строго под уровнем воды в i-й день. Определите минимально возможную сумму величин di по всем дням. Изначально (перед первым днем) на берегу нет отметок.
Выходные данные
Выведите одно целое число — минимально возможную сумму количества отметок строго под уровнем воды по всем дням.
Примечание
Рисунок ниже показывает оптимальный случай в первом примере.
Обратите внимание: в день 3 должна быть создана новая отметка, иначе в день 4 не будет 3 отметки над уровнем воды. Суммарное количество отметок под водой в этом случае равно 0 + 0 + 2 + 0 + 3 + 1 = 6.
Рисунок ниже показывает оптимальный случай во втором примере.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
0 1 0 3 0 2
|
6
|
|
2
|
5
0 1 2 1 2
|
1
|
|
3
|
5
0 1 1 2 2
|
0
|