← 返回题目列表

AtCoder · abc176_c

C. 步骤

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

分数: 300 点

问题陈述

N 人们站成一排。的高度 i前面数第一个人是 A_i.

我们希望每个人都站在一定高度的凳子上 - 至少为零 - 以便每个人都满足以下条件:

条件:此人面前没有人比此人高。这里,人的高度包括凳子。

找出实现这一目标所需的凳子的最小总高度。

约束

  • 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 每个人都会工作。