P12663 [KOI 2023 Round 2] 湖边的蚁穴

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

KOI 湖畔有一个蚂蚁们聚居的蚁穴。这个蚁穴沿着圆形湖泊的边缘，环形地依次排列着从 $1$ 到 $N$ 编号的 $N$ 个房间。对于所有满足 $1 \leq i \leq N - 1$ 的 $i$，第 $i$ 个房间与第 $i + 1$ 个房间之间，以及第 $N$ 个房间与第 $1$ 个房间之间都通过通道直接连接。 但由于各种原因，从某些房间开始分出了若干个小房间。现在，对于所有满足 $1 \leq i \leq N$ 的 $i$，蚁穴中的第 $i$ 个房间通过通道直接连接着 $C_i$ 个小房间。与第 $i$ 个房间连接的小房间不会与其他任何房间相连。 例如，若 $N = 7$ 且 $C = [3, 0, 0, 1, 0, 2, 0]$，蚁穴的结构如下图所示。  蚁穴中的每个房间与小房间最多只能住一只蚂蚁。如果通道直接连接的两个位置（房间或小房间）中都住着蚂蚁，那么这两只蚂蚁会感到不舒服。为了避免这种不适，当前蚁穴的每条通道最多只能连接一只住着蚂蚁的位置。 蚂蚁们非常聪明，因此在上述条件允许的情况下，它们总是设法使蚁穴中居住的蚂蚁数量最大。现在给出蚁穴的结构，请编写一个程序，计算最多有多少只蚂蚁可以住在蚁穴中。

第一行输入一个整数 $N$。 第二行输入 $C_1, C_2, \dots, C_N$，表示每个房间连接的小房间数量，整数之间以空格分隔。

输出一个整数，表示最多可以居住在蚁穴中的蚂蚁数量。

**限制条件** - 所有给定的数均为整数。 - $2 \leq N \leq 250\,000$ - $0 \leq C_i \leq 10^{12} \quad (1 \leq i \leq N)$ **子任务** 1. （4 分）$N = 2$ 2. （8 分）$N \leq 1\,000$ 且 $C_i = 0 \quad (1 \leq i \leq N)$ 3. （14 分）$N \leq 1\,000$ 且 $C_i \leq 1 \quad (1 \leq i \leq N)$ 4. （15 分）$N \leq 1\,000$ 5. （20 分）$C_i \leq 1 \quad (1 \leq i \leq N)$ 6. （13 分）$C_i \leq 1\,000 \quad (1 \leq i \leq N)$ 7. （9 分）$C_i \geq 1 \quad (1 \leq i \leq N)$ 8. （17 分）无附加限制 翻译由 ChatGPT-4o 完成