← 返回题目列表

Codeforces · 205/B

B. 小象和排序

中文机器翻译题面 查看原题

小象喜欢分类。

他有一个由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]。