種菜好好玩(Growing Vegetables is Fun 4)
發布時間: Feb. 20, 2021, 2:09 a.m. 最後更新時間: Sept. 14, 2023, 10:52 p.m. 時間限制: 4000ms 記憶體限制: 128M
ビ太郎喜歡園藝。他現在要在花園種一種叫做ビバ草的植物。花園裡有$N$株ビバ草，他們沿著西到東排成一直線。並且編號為$1$到$N$。目前第$i$株的高度為$A_i$。
因為這些是被品種改良過的植物，只要ビ太郎給ビバ草澆水一次，那一株的高度就會增加1。因為ビ太郎想要好好的裝飾這花園，所以他想要使得他的植物們滿足以下條件
- 設$B_i$為ビ太郎完成澆水第$i$株ビバ草的高度。存在正整數$k(1\le k\le N)$滿足$B_j < B_{j+1}(1\le j\le k-1)$，且滿足$B_j > B_{j+1}(k\le j\le N-1)$
然而，ビ太郎並不擅長澆水，所以每當他要給ビバ草澆水時，他只能給一段連續的區間澆水。也就是說，他會選定兩個正整數$L, R(1\le L\le R\le N)$並且給$L, L+1, ..., R$澆水。
ビ太郎想要最小化澆水的次數。
請寫一個程式能在給定$N$與每個$A_i$的情況下，計算出ビ太郎最小需要澆多少次水才能滿足上面的條件。
輸入第一行有一個整數$N(2\le N\le 2\cdot 10^5)$。
第二行有$N$個整數$a_i(1\le A_i\le 10^9$。
輸出一行包含一個數字，代表最少操作次數。
複製範例
5 3 2 2 3 1
3
複製範例
5 9 7 5 3 1
0
複製範例
2 2021 2021
1
複製範例
8 12 2 34 85 4 91 29 85
93
