CF1674E.Breaking the Wall

Monocarp plays "Rage of Empires II: Definitive Edition" — a strategic computer game. Right now he's planning to attack his opponent in the game, but Monocarp's forces cannot enter the opponent's territory since the opponent has built a wall.

The wall consists of $n$ sections, aligned in a row. The $i$-th section initially has durability $a_i$. If durability of some section becomes $0$ or less, this section is considered broken.

To attack the opponent, Monocarp needs to break at least two sections of the wall (any two sections: possibly adjacent, possibly not). To do this, he plans to use an onager — a special siege weapon. The onager can be used to shoot any section of the wall; the shot deals $2$ damage to the target section and $1$ damage to adjacent sections. In other words, if the onager shoots at the section $x$, then the durability of the section $x$ decreases by $2$, and the durability of the sections $x - 1$ and $x + 1$ (if they exist) decreases by $1$ each.

Monocarp can shoot at any sections any number of times, he can even shoot at broken sections.

Monocarp wants to calculate the minimum number of onager shots needed to break at least two sections. Help him!

Monocarp 正在玩《帝国时代 II：决定版》——一款策略类电脑游戏。此时他正计划在游戏中进攻对手，但 Monocarp 的部队无法进入对手的领地，因为对手已修建了一堵墙。

这堵墙由 $n$ 个并排排列的段组成。第 $i$ 段初始耐久度为 $a_i$。若某一段的耐久度降至 $0$ 或更低，则该段被视为已被击破。

为了进攻对手，Monocarp 至少需要击破墙上的两段（任意两段均可：可以相邻，也可以不相邻）。为此，他计划使用一种名为“投石机”（onager）的特殊攻城武器。投石机可向墙的任意一段发射；一次射击对目标段造成 $2$ 点伤害，并对其左右相邻段（若存在）各造成 $1$ 点伤害。换言之，若投石机射击第 $x$ 段，则第 $x$ 段的耐久度减少 $2$，而第 $x-1$ 段和第 $x+1$ 段（若存在）的耐久度各减少 $1$。

Monocarp 可以向任意段发射任意次数的投石机，甚至可以向已被击破的段继续射击。

Monocarp 希望计算出击破至少两段墙所需的最少投石机射击次数。请帮助他！

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of sections.

The second line contains the sequence of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the initial durability of the $i$-th section.

第一行包含一个整数 $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$ 个区段的初始耐久度。

Print one integer — the minimum number of onager shots needed to break at least two sections of the wall.

输出一个整数——摧毁城墙至少两个区段所需的最小投石机射击次数。

In the first example, it is possible to break the $2$-nd and the $4$-th section in $10$ shots, for example, by shooting the third section $10$ times. After that, the durabilities become $[20, 0, 10, 0, 20]$. Another way of doing it is firing $5$ shots at the $2$-nd section, and another $5$ shots at the $4$-th section. After that, the durabilities become $[15, 0, 20, 0, 15]$.

In the second example, it is enough to shoot the $2$-nd section once. Then the $1$-st and the $3$-rd section will be broken.

In the third example, it is enough to shoot the $2$-nd section twice (then the durabilities become $[5, 2, 4, 8, 5, 8]$), and then shoot the $3$-rd section twice (then the durabilities become $[5, 0, 0, 6, 5, 8]$). So, four shots are enough to break the $2$-nd and the $3$-rd section.

在第一个例子中，可以通过射击第 3 个区域 10 次，用 10 发子弹击破第 2 和第 4 个区域。之后，各区域的耐久度变为 $[20, 0, 10, 0, 20]$。另一种方法是向第 2 个区域射击 5 次，再向第 4 个区域射击 5 次。之后，各区域的耐久度变为 $[15, 0, 20, 0, 15]$。

在第二个例子中，仅需向第 2 个区域射击 1 次，即可使第 1 和第 3 个区域被击破。

在第三个例子中，先向第 2 个区域射击 2 次（此时耐久度变为 $[5, 2, 4, 8, 5, 8]$），再向第 3 个区域射击 2 次（此时耐久度变为 $[5, 0, 0, 6, 5, 8]$），即可击破第 2 和第 3 个区域。因此，共需 4 发子弹。