A nursery keeps n seedling pots in a single row, numbered left to right, each currently holding a seedling of some height in centimeters. The nursery's grow-lamp can apply a growth boost to any one pot at a time; each boost increases that seedling's height by exactly 1 cm, and boosts can be applied any number of times (including zero) to any pot, in any order. The nursery wants the row of heights to read strictly increasing from left to right -- every seedling strictly taller than the one immediately to its left. Find the minimum total number of growth boosts needed to achieve this.
The first line contains a single integer n, the number of pots.
The second line contains n integers, the current height of each pot in centimeters, left to right.
Print a single integer: the minimum total number of growth boosts required so the heights are strictly increasing left to right.
Example 1
Input
3 1 1 1
Expected
3
Explanation
Heights are 1, 1, 1. The first pot stays at 1. The second pot must become strictly taller than 1, so it needs 1 boost to reach 2. The third pot must become strictly taller than the (now) 2, so it needs 2 boosts to reach 3. Total boosts: 1+2=3.
Example 2
Input
5 1 5 2 4 1
Expected
14
Explanation
Heights are 1, 5, 2, 4, 1. The first pot stays at 1. The second pot (5) is already taller than 1, so it stays at 5 with 0 boosts. The third pot (2) must exceed 5, so it needs 4 boosts to reach 6. The fourth pot (4) must exceed 6, so it needs 3 boosts to reach 7. The fifth pot (1) must exceed 7, so it needs 7 boosts to reach 8. Total boosts: 0+4+3+7=14.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →