Bitaro 喜欢园艺。他现在在花园里种植一种叫做 Biba-herb 的植物。花园里有 $N$ 株 Biba-herb，从西向东排成一行。这些 Biba-herb 从西向东依次编号为 $1$ 到 $N$。现在，第 $i$ 株 Biba-herb ($1 \le i \le N$) 的高度为 $A_i$。

由于品种改良，如果 Bitaro 给一株 Biba-herb 浇一次水，它的高度就会增加 $1$。因为他想装饰花园，所以他会多次给 Biba-herb 浇水，以满足以下条件：

• 在 Bitaro 完成浇水后，设 $B_i$ 为第 $i$ 株 Biba-herb 的高度。那么，存在一个整数 $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-herb 浇水时，他只能给一个区间内的连续 Biba-herb 浇水。换句话说，他选择整数 $L$ 和 $R$ ($1 \le L \le R \le N$)，并给第 $L, L + 1, \dots, R$ 株 Biba-herb 浇水。

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

请编写一个程序，给定 Biba-herb 的数量及其当前高度，计算满足上述条件的最小浇水次数。

输入格式

从标准输入读取以下数据。给定的值均为整数。

$N$ $A_1 \dots A_N$

输出格式

向标准输出写入一行。输出应包含最小的浇水次数。

数据范围

• $2 \le N \le 200\,000$。
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$)。

子任务

1. (40 分) $N \le 2\,000$。
2. (60 分) 无附加限制。

样例

样例输入 1

5
3 2 2 3 1

样例输出 1

3

说明 1

如果 Bitaro 按以下方式浇水三次，则满足条件：

• 令 $L = 2$，$R = 5$。Bitaro 给第 $2, 3, 4, 5$ 株 Biba-herb 浇水。从西向东，Biba-herb 的高度变为 $3, 3, 3, 4, 2$。
• 令 $L = 2$，$R = 3$。Bitaro 给第 $2, 3$ 株 Biba-herb 浇水。从西向东，Biba-herb 的高度变为 $3, 4, 4, 4, 2$。
• 令 $L = 3$，$R = 3$。Bitaro 给第 $3$ 株 Biba-herb 浇水。从西向东，Biba-herb 的高度变为 $3, 4, 5, 4, 2$。

如果 Bitaro 浇水次数少于三次，则无法满足条件。因此，最小浇水次数为 $3$。

样例输入 2

5
9 7 5 3 1

样例输出 2

0

说明 2

由于条件已经满足，最小浇水次数为 $0$。

样例输入 3

2
2021 2021

样例输出 3

1

说明 3

如果 Bitaro 选择 $L = 1$，$R = 1$ 给第 $1$ 株 Biba-herb 浇水，或者选择 $L = 2$，$R = 2$ 给第 $2$ 株 Biba-herb 浇水，则满足条件。

样例输入 4

8
12 2 34 85 4 91 29 85

样例输出 4

93