/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
N 人が 1 列に並んでおり、前から i 番目の人の身長は A_i です。
それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。
条件：踏み台を込めて身長を比較したとき、自分より前に、自分より背の高い人が存在しない
この条件を満たす時の、踏み台の高さの合計の最小値を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
踏み台の高さの合計の最小値を出力せよ。
入力例 1
5 2 1 5 4 3
出力例 1
4
それぞれ、高さ 0,1,0,1,2 の踏み台を与えると、踏み台を込めた身長は 2,2,5,5,5 となり、条件を満たします。
踏み台の高さの合計をこれより小さくすることはできません。
入力例 2
5 3 3 3 3 3
出力例 2
0
全員に高さ 0 の踏み台を与えればよいです。
Score : 300 points
Problem Statement
N persons are standing in a row. The height of the i-th person from the front is A_i.
We want to have each person stand on a stool of some heights - at least zero - so that the following condition is satisfied for every person:
Condition: Nobody in front of the person is taller than the person. Here, the height of a person includes the stool.
Find the minimum total height of the stools needed to meet this goal.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the minimum total height of the stools needed to meet the goal.
Sample Input 1
5 2 1 5 4 3
Sample Output 1
4
If the persons stand on stools of heights 0, 1, 0, 1, and 2, respectively, their heights will be 2, 2, 5, 5, and 5, satisfying the condition.
We cannot meet the goal with a smaller total height of the stools.
Sample Input 2
5 3 3 3 3 3
Sample Output 2
0
Giving a stool of height 0 to everyone will work.