题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

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$，表示每个房间连接的小房间数量，整数之间以空格分隔。

输出格式

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

4
1 0 1 0

4

4
1 1 1 1

4

2
0 0

1

7
3 0 0 1 0 2 0

9

提示

限制条件

• 所有给定的数均为整数。
• $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 完成