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