CF1674E Breaking the Wall

Monocarp 正在玩《Rage of Empires II: Definitive Edition》——一款策略类电脑游戏。现在他计划进攻游戏中的对手，但由于对手修建了一道城墙，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 \times 10^5$），表示城墙的段数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$），其中 $a_i$ 表示第 $i$ 段的初始耐久度。

输出一个整数，表示至少破坏两段城墙所需的最少抛石机攻击次数。

在第一个样例中，可以通过对第 $3$ 段攻击 $10$ 次来破坏第 $2$ 段和第 $4$ 段。此时各段耐久度变为 $[20, 0, 10, 0, 20]$。另一种做法是分别对第 $2$ 段和第 $4$ 段各攻击 $5$ 次，此时各段耐久度变为 $[15, 0, 20, 0, 15]$。 在第二个样例中，只需对第 $2$ 段攻击一次，第 $1$ 段和第 $3$ 段就会被破坏。 在第三个样例中，只需先对第 $2$ 段攻击两次（此时耐久度变为 $[5, 2, 4, 8, 5, 8]$），再对第 $3$ 段攻击两次（此时耐久度变为 $[5, 0, 0, 6, 5, 8]$），共 $4$ 次攻击即可破坏第 $2$ 段和第 $3$ 段。 由 ChatGPT 4.1 翻译