First, you have to realize the following points:

• If there is a person higher than you in front of you, then you have to use a stool to increase your height.
• By increasing your height, people behind you will never benefit from it in such way like “they don’t have to increase their height.” (On the other hand, they may have to use stool because of you.)

With the observations above, we can predict that it is optimal for every person to use the least high stool as possible.

Let us consider how much the \(i\)-th person has to use the stool. If there is a person higher than the person, then the \(i\)-th person has to become as high as the person using a stool. Therefore, the neccessary height \(B_i\) that \(i\)-th person has to have is

\(B_i = \max(A_1, A_2, ... , A_i).\)

The sequence \(B\) constructed by equation above is a monotonic non-decreasing sequence. Therefore the neccesary condition and sufficient condition agreed, so we can see that reaching the sequence \(B\) is the optimal.

If they are calculated naively, the time complexity will be \(O(N^2)\). However, updating the maximum value while calculating from the beginning enables to eliminate the process of finding maximum by iterating through loop every time, and therefore to calculate in a total of \(O(N)\) time.

Note that the answer will become so large that it won’t fit in a 32-bit variable. Sample Code(C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	long long ans = 0;
	int MaxNum = 0;
	for (int i = 0; i < N; i++)
	{
		//Use common MaxNum to reduce the compuation time
		MaxNum = max(MaxNum, A[i]);
		int Bi = MaxNum;
		ans += Bi - A[i];
	}

	cout << ans << endl;
}