家庭菜园

現在是秋天，家庭菜園對我來說是一個很有趣的嗜好。我在家裡的花園裡種植了一種叫做「活力草」的植物。花園裡有 $N$ 株活力草，按照東西方向排列成一行，從西邊開始編號為 $1$ 到 $N$。現在，活力草 $i$（$1 \leqq i \leqq N$）的高度是 $A_i$。

由於這種活力草經過特殊的品種改良，每次給它們澆水時，它們的高度就會增長 $1$ 單位。為了讓花園看起來更美觀，我想要進行多次澆水，並滿足以下條件：

• 對於澆水後的活力草 $i$（$1 \leqq i \leqq N$），令其高度為 $B_i$。這樣的整數 $k$（$1 \leqq k \leqq N$）存在，滿足「對於 $1 \leqq j \leqq k - 1$，有 $B_j < B_{j + 1}$ 」和「對於 $k \leqq j \leqq N - 1$，有 $B_j > B_{j + 1}$」。

然而，由於我的不靈巧，每次澆水只能給一段區間的活力草一起澆水。也就是說，每次澆水時，我可以選擇一個整數區間 $L, R$（$1 \leqq L \leqq R \leqq N$），並給活力草 $L, L + 1, \ldots, R$ 澆水。

我希望盡可能少地進行澆水。

請根據給定的活力草數量和目前高度的信息，編寫一個程序來求出滿足條件所需的最少澆水次數。

---

輸入

輸入從標準輸入中以以下格式給出。所有的輸入均為整數。

$N$ $A_1$ $\cdots$ $A_N$

輸出

請在標準輸出中打印出滿足條件所需的最少澆水次數，只輸出一行。

---

約束條件

• $2 \leqq N \leqq 200,000$。
• $1 \leqq A_i \leqq 1,000,000,000$（$1 \leqq i \leqq N$）。

子問題

1. （40 分）$N \leqq 2,000$。
2. （60 分）沒有額外的約束條件。

---

示例

輸入示例 1

5
3 2 2 3 1

輸出示例 1

3

通過進行 $3$ 次澆水，可以滿足條件：

• 將 $L=2$，$R=5$，給活力草 $2, 3, 4, 5$ 澆水。活力草的高度從西到東分別為 $3, 3, 3, 4, 2$。
• 將 $L=2$，$R=3$，給活力草 $2, 3$ 澆水。活力草的高度從西到東分別為 $3, 4, 4, 4, 2$。
• 將 $L=3$，$R=3$，給活力草 $3$ 澆水。活力草的高度從西到東分別為 $3, 4, 5, 4, 2$。

由於無法在 $2$ 次或更少的澆水中滿足條件，所以最少澆水次數為 $3$。

---

輸入示例 2

5
9 7 5 3 1

輸出示例 2

0

由於已經滿足了條件，所以最少澆水次數為 $0$。

---

輸入示例 3

2
2021 2021

輸出示例 3

1

要滿足條件，可以進行 $1$ 次澆水，選擇 $L = 1$，$R = 1$，給活力草 $1$ 澆水，或者選擇 $L = 2$，$R = 2$，給活力草 $2$ 澆水。

---

輸入示例 4

8
12 2 34 85 4 91 29 85

輸出示例 4

93