#P18259. Cows

Cows

Cows

一片狭长的牧场被分成连续编号为 1,2,…,n1,2,\ldots,n 的 nn 个区段。第 ii 个区段的草最初高为 hih_i,每个区段里有一头牛。

区段之间有围栏,牛不能走到其他区段,但可以把头伸过围栏吃相邻区段的草。对于 1≤i<n1\le i<n,第 ii 与第 i+1i+1 个区段相邻;首尾区段不相邻。

每一分钟,所有牛同时行动。 每头牛按照这一分钟开始时的草高选择一个区段:

  • 如果自己的区段还有草,这头牛必须吃自己区段的草。
  • 否则,它选择一个仍有草的相邻区段吃草。
  • 如果自己和相邻区段都没有草,它就不做任何事。

如果某一分钟有 xx 头牛吃同一个区段的草,该区段的草高减少 xx,但不会低于 00,即更新为 max⁡(0,hi−x)\max(0,h_i-x)。这一分钟吃完草的牛,要到下一分钟才可能帮助相邻区段。

所有牛相互合作,希望尽快吃完牧场中的全部草。求至少需要多少分钟。

输入格式

第一行包含一个整数 nn,表示区段数量。

第二行包含 nn 个整数 h1,h2,…,hnh_1,h_2,\ldots,h_n,表示各区段最初的草高。

输出格式

输出一个整数,表示吃完全部草所需的最少分钟数。

数据范围

  • 1≤n≤200 0001\le n\le200\,000;
  • 0≤hi≤1090\le h_i\le10^9;
  • 至少有一个 hi>0h_i>0;
  • 输入只有一组数据。

样例 1

5
5 4 0 4 6
4

一种最优策略如下,数组表示各分钟开始前或完成后的草高:

  1. 初始为 [5,4,0,4,6][5,4,0,4,6]。第3头牛选择第4段,其他牛吃自己的草,得到 [4,3,0,2,5][4,3,0,2,5]。
  2. 第3头牛继续选择第4段,得到 [3,2,0,0,4][3,2,0,0,4]。
  3. 第3头牛选择第2段,第4头牛选择第5段,得到 [2,0,0,0,2][2,0,0,0,2]。
  4. 第2头牛选择第1段,第4头牛选择第5段,第3头牛不行动,得到 [0,0,0,0,0][0,0,0,0,0]。

样例 2

3
1 4 6
5

本例中牛始终没有选择余地,过程为

$$[1,4,6]\to[0,3,5]\to[0,1,4]\to[0,0,3]\to[0,0,1]\to[0,0,0].$$