小象喜欢分类。
他有一个由n个整数组成的数组a。让我们将数组元素从 1 到 n 编号,那么第 i 个元素将表示为 ai。小象可以一步选择任意一对整数 l 和 r (1 ≤ l ≤ r ≤ n),并对所有 i 将 ai 加 1,使得 l ≤ i ≤ r。
帮助小象找到将数组 a 转换为按非降序排序的任意数组所需的最少移动次数。数组 a 由 n 个元素组成,如果对于任何 i (1 ≤ i < n) ai ≤ ai + 1 成立,则按非降序排序。
输入
第一行包含一个整数 n (1 ≤ n ≤ 105) — 数组 a 的大小。下一行包含 n 个整数,用单个空格分隔 — 数组 a (1 ≤ ai ≤ 109)。数组元素按照索引递增的顺序列在行中。
输出
在一行中打印一个整数——问题的答案。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
3 1 2 3
输出 #1
0
输入 #2
3 3 2 1
输出 #2
2
输入 #3
4 7 4 1 47
输出 #3
6
注意
在第一个示例中,数组已按非降序排序,因此答案为 0。
在第二个示例中,您需要执行两个操作:首先将数字从第二个增加到第三个(之后数组将是:[3, 3, 2]),第二个仅增加最后一个元素(数组将是:[3, 3, 3])。
在第三个示例中,您应该至少执行 6 个步骤。可能的操作顺序是:(2;3)、(2;3)、(2;3)、(3;3)、(3;3)、(3;3)。之后数组转换为 [7, 7, 7, 47]。