[AdditionalFile3468.zip](file://AdditionalFile3468.zip?type=additional_file)

P7404 [JOI 2021 Final] 有趣的家庭菜园 4 / Growing Vegetables is Fun 4

题目描述

给定一个长为 $N$ 的序列 $A$，你可以进行若干次操作：

• 选定一个区间 $[L,R]$，让这个区间里的数加 $1$。

设经过这若干次操作后的序列为 $B$，那么你需要让 $B$ 满足下面这个要求：

• 存在一个整数 $k \in [1,N]$，满足对于子序列 $A_1=\{B_1,B_2,\cdots,B_k\}$ 为严格递增序列，对于子序列 $A_2=\{B_k,B_{k+1},\cdots,B_N\}$ 为严格递减序列。

你想知道最少需要多少次操作才能满足上面这个要求。

输入格式

第一行一个整数 $N$ 代表序列长度。

第二行 $N$ 个整数，代表序列 $A$。

输出格式

一行一个整数代表最小操作次数。

输入输出样例 #1

输入 #1

5
3 2 2 3 1

输出 #1

3

输入输出样例 #2

输入 #2

5
9 7 5 3 1

输出 #2

0

输入输出样例 #3

输入 #3

2
2021 2021

输出 #3

1

输入输出样例 #4

输入 #4

8
12 2 34 85 4 91 29 85

输出 #4

93

说明/提示

样例 1 解释

• 对 $[2,5]$ 进行操作，序列变为 $\{3,3,3,4,2\}$。
• 对 $[2,3]$ 进行操作，序列变为 $\{3,4,4,4,2\}$。
• 对 $[3,3]$ 进行操作，序列变为 $\{3,4,5,4,2\}$。

样例 2 解释

序列已经满足要求，不需要操作。

样例 3 解释

对区间 $[1,1]$ 或 $[2,2]$ 进行操作都可。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（40 pts）：$N \le 2000$。
• Subtask 2（60 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$，$1 \le A_i \le 10^9$。

说明

翻译自 The 20th Japanese Olympiad in Informatics Final Round A とてもたのしい家庭菜園 4 的英文翻译 Growing Vegetables is Fun 4。

#3468. 「JOI 2021 Final」有趣的家庭菜园 4

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

译自 JOI 2021 Final T1「とてもたのしい家庭菜園 4 / Growing Vegetables is Fun 4」

Bitaro 喜欢园艺。他现在正在自己的花园种 Biba 草。在他的花园中共种有 $N$ 棵 Biba 草，从西向东种成一行。Biba 草自西向东从 $1$ 到 $N$ 编号。现在，第 $i$ 棵 Biba 草的高度是 $A_i$。

由于品种改良，如果 Bitaro 给一棵 Biba 草浇一次水，那么这棵 Biba 草的高度就增加 $1$。因为他想装饰他的花园，他会给这些 Biba 草浇若干次水，使其满足以下条件：

• 在 Bitaro 浇水后，令 $B_i$ 为第 $i$ 棵 Biba 草的高度。那么存在一个整数 $k\ (1\le k\le N)$，满足对于任意 $1\le j\le k-1$，都有 $B_j<B_{j+1}$，对于任意 $k\le j\le N-1$，都有 $B_j>B_{j+1}$。

然而，Bitaro 不擅长浇水。当他要给 Biba 草浇水时，他只能给在一段区间内的 Biba 草浇水。也就是说，他会选择两个整数 $L$ 和 $R$（$1\le L\le R\le N$）并且给第 $L,L+1,\ldots ,R$ 棵 Biba 草浇水。

Bitaro 想要最小化浇水的次数。

给出 Biba 草的棵数和它们目前的高度，写一个程序计算最少需要浇多少次水才能满足以上条件。

输入格式

第一行一个整数 $N$；

第二行 $N$ 个整数 $A_i$。

输出格式

输出一行一个整数，表示浇水的最少次数。

样例 1

输入

5
3 2 2 3 1

输出

3

如果 Bitaro 按如下方法浇三次水，就可以满足条件：

• 令 $L=2,R=5$。Bitaro 会给第 $2,3,4,5$ 棵 Biba 草浇水。Biba 草的高度自西向东变为 $3,3,3,4,2$。

• 令 $L=2,R=3$。Bitaro 会给第 $2,3$ 棵 Biba 草浇水。Biba 草的高度自西向东变为 $3,4,4,4,2$。

• 令 $L=3,R=3$。Bitaro 会给第 $3$ 棵 Biba 草浇水。Biba 草的高度自西向东变为 $3,4,5,4,2$。

如果 Bitaro 浇水次数少于 $3$，则不可能满足条件。所以最少的浇水次数为 $3$。

样例 2

输入

5
9 7 5 3 1

输出

0

因为本身就已经满足条件，所以最少浇水次数为 $0$。

样例 3

输入

2
2021 2021

输出

1

Bitaro 选择 $L=1,R=1$ 给第 $1$ 棵 Biba 草浇水，或选择 $L=2,R=2$ 给第 $2$ 棵 Biba 草浇水都可以满足条件。

样例 4

输入

8
12 2 34 85 4 91 29 85

输出

93

数据范围与提示

对于所有数据，$2\le N\le 2\times 10^5,1\le A_i\le 10^9$。

子任务附加限制及分值如下：

• 子任务 1（$40$ 分）：$N\le 2\ 000$；
• 子任务 2（$60$ 分）：无附加限制。