まず、考えるべき事は、以下のようなことです。

• 自分より背の高い人が前にいる時、自分は踏み台を使って背を高くしなければならない。
• 自分の背が高くなることにより、後ろの人が「背が低いままで良い」などの得をすることは起こらない。（逆に踏み台を使わないといけなくなることは起こりうる）

以上を踏まえて、各人がそれぞれ出来るだけ踏み台を使わないようにするのが最善であることが予想できます。

\(i\) 番目がどれだけ踏み台を使うべきかについて考えてみましょう。自分より背が高い人がいるのであれば、踏み台を使って、その高さ以上にならなければなりません。つまり、\(i\)番目の人が最低限持つべき身長 \(B_i\)は、

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

であると言えます。この数列 \(B\) を考えた時、これは広義単調増加となっています。よって、必要条件と十分条件が一致したため、この \(B\) を目指すことが最善であることがわかります。

これを愚直に計算すると、計算量は \(O(N^2)\) となってしまいます。ですが、前から順番に最大値を持ちながら計算することで、毎回ループを回して最大値を計算する必要がなくなり、\(O(N)\)で計算することが可能となります。

答えは非常に大きくなるため、32bit変数では収まりきらないことに注意しましょう。

回答例(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++)
	{
		//MaxNumを使い回すことで計算を抑える
		MaxNum = max(MaxNum, A[i]);
		int Bi = MaxNum;
		ans += Bi - A[i];
	}

	cout << ans << endl;
}