台阶

题目描述

有 $N$ 个人排成一列,从前往后数第 $i$ 个人的身高是 $A_i$。

想在每个人的脚下放置高度为 $0$ 以上的踏台,使所有人都满足以下条件:

条件:把踏台高度算进身高进行比较时,自己前面不存在比自己更高的人。

求满足该条件时,踏台高度的总和的最小值。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $\ldots$ $A_N$

输出格式

输出踏台高度的总和的最小值。

样例

5
2 1 5 4 3

4

分别给高度为 $0,1,0,1,2$ 的踏台后,算上踏台的身高为 $2,2,5,5,5$,满足条件。

无法使踏台高度的总和比这更小。

5
3 3 3 3 3

0

给所有人高度为 $0$ 的踏台即可。

数据范围

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入均为整数