DMOPC '18 Contest 2 P2 - Booster Cushions

View as PDF

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

At the Nova Theatre, the balcony seats can be seen as a grid with rows and columns. The plays are popular and people have bought tickets to see the next one. However, these tickets do not have set seats yet. Administration has decided to start selling booster cushions and will be rearranging people's seats to maximize their profit. In particular, an audience member can only see the play if their height is strictly more than the person in the seat directly in front. Otherwise, they will purchase cushions until they can. Each cushion increases their height by exactly centimeter. Note that an audience member who is in the front row or not seated directly behind anyone has no need for cushions. Given the heights of the people in centimeters, find the maximum number of cushions that can be sold.

Constraints

The heights in centimeters are guaranteed to be integers from to .

Input Specification

The first line will contain three space-separated integers, .
The next line will contain space-separated integers, the heights of the people in centimeters.

Output Specification

Output the maximum number of cushions that can be sold after arranging people's seats.

Sample Input 1

2 7 4
250 200 150 100

Sample Output 1

202

Explanation for Sample 1

Seat the audience like so:

250  200  X  X  X  X  X
150  100  X  X  X  X  X

Then the two in the back two seats must each purchase cushions, giving an answer of .

Sample Input 2

5 1 4
100 100 100 100

Sample Output 2

6

Explanation for Sample 2

Seat the audience like so:

X
100
100
100
100

The first person has nobody in front of them, so they purchase cushions.
The next person must purchase cushion and now has a height of .
Then the third person must purchase cushions and now has a height of .
Finally, the last person must purchase cushions and now has a height of .