Monocarp 玩“帝国之怒 II:最终版”——一款战略电脑游戏。现在他正计划在游戏中攻击对手,但Monocarp的部队无法进入对手的领地,因为对手已经筑起了城墙。
墙由 $$$n$$$ 部分组成,并排成一排。第 $$$i$$$ 部分最初具有耐用性 $$$a_i$$$。如果某些部分的耐用性变为 $$$0$$$ 或更少,则该部分被视为损坏。
要攻击对手,Monocarp 需要打破至少两部分墙(任何两部分:可能相邻,可能不相邻)。为此,他计划使用投石机——一种特殊的攻城武器。投石机可以用来射击墙壁的任何部分;射击对目标部分造成 $$$2$$$ 伤害,对相邻部分造成 $$$1$$$ 伤害。换句话说,如果投石机射击 $$$x$$$ 部分,则 $$$x$$$ 部分的耐久性会减少 $$$2$$$,$$$x - 1$$$ 和 $$$x + 1$$$ 部分(如果存在)的耐久性各减少 $$$1$$$。
Monocarp可以对任何部分进行任意次数的射击,他甚至可以对破碎的部分进行射击。
Monocarp 希望计算打破至少两个部分所需的最小投石机射击次数。帮助他!
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 节数。
第二行包含整数序列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 部分的初始持久性。
输出
打印一个整数——打破至少两段墙所需的投石机射击的最少数量。
示例
输入 #1
5 20 10 30 10 20
输出 #1
10
输入 #2
3 1 8 1
输出 #2
1
输入 #3
6 7 6 6 8 5 8
输出 #3
4
输入#4
6 14 3 8 10 15 4
输出#4
4
输入 #5
4 1 100 100 1
输出 #5
2
输入 #6
3 40 10 10
输出 #6
7
注意
在第一个示例中,可以在 $$$10$$$ 镜头中打破 $$$2$$$-nd 和 $$$4$$$-th 部分,例如,通过拍摄第三部分 $$$10$$$ 次。之后,耐久性变为 $$$[20, 0, 10, 0, 20]$$$。另一种方法是在第 $$$2$$$ 区域发射 $$$5$$$ 子弹,并在第 $$$4$$$ 区域发射 $$$5$$$ 子弹。之后,耐久性变为 $$$[15, 0, 20, 0, 15]$$$。
在第二个示例中,拍摄 $$$2$$$-nd 部分一次就足够了。然后 $$$1$$$-st 和 $$$3$$$-rd 部分将被破坏。
在第三个例子中,将$$$2$$$-nd部分拍摄两次就足够了(然后耐久性变为$$$[5, 2, 4, 8, 5, 8]$$$),然后将$$$3$$$-rd部分拍摄两次(然后耐久性变为$$$[5, 0, 0, 6, 5, 8]$$$)。因此,四次射击足以打破 $$$2$$$-nd 和 $$$3$$$-rd 部分。