AT_joi2026_yo2_b 究極の団子職人 (Ultimate Dango Maker)

JOI 君是一名团子工匠。有 $N$ 种颜色的团子，颜色编号从 $1$ 到 $N$，JOI 君拥有颜色 $i$（$1 \leq i \leq N$）的团子 $A_i$ 个。 JOI 君可以从他拥有的团子中选择 $3$ 个，制作一串**串团子**。但选择的 $3$ 个团子的颜色 $c_1, c_2, c_3$（$1 \leq c_1 \leq N$，$1 \leq c_2 \leq N$，$1 \leq c_3 \leq N$）需要满足：$c_1$ 与 $c_2$ 的差、$c_2$ 与 $c_3$ 的差、$c_3$ 与 $c_1$ 的差都不超过 $1$，即以下条件全部满足： - $|c_1 - c_2| \leq 1$ - $|c_2 - c_3| \leq 1$ - $|c_3 - c_1| \leq 1$ 同一个团子不能在多串串团子中重复使用。JOI 君希望通过巧妙选择团子，使制作的串团子数目尽可能多。 请你根据所给团子的信息，计算 JOI 君最多可以制作多少串串团子。

输入如下格式： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出 JOI 君最多能制作的串团子数，输出一行。

## 小子任务 1. ($6$ 分) $N=1$。 2. ($9$ 分) $N \leq 2$。 3. ($10$ 分) 所有 $A_i$ 都是 $3$ 的倍数（$1 \leq i \leq N$）。 4. ($17$ 分) $A_i = 2$（$1 \leq i \leq N$）。 5. ($21$ 分) $A_i \leq 3$（$1 \leq i \leq N$）。 6. ($37$ 分) 无额外限制。 ## 样例解释 1 可以用颜色 $1$ 的团子 $3$ 个做 $1$ 串，用颜色 $2$ 的团子 $1$ 个和颜色 $3$ 的团子 $2$ 个做 $1$ 串，共制作 $2$ 串串团子。第一串 $|1-1|=0\leq1$，第二串 $|2-3|\leq 1$，$|3-3|\leq 1$，所以团子的选择满足条件。不能制作超过 $2$ 串，因此输出 $2$。 该样例满足小子任务 $5, 6$ 的约束。 ## 样例解释 2 可以用颜色 $1$ 的团子每 $3$ 个做 $1$ 串，总共 $33$ 串。不能制作更多串串团子，因此输出 $33$。 该样例满足小子任务 $1, 2, 3, 6$ 的约束。 ## 样例解释 3 可以用颜色 $1$ 的团子 $3$ 个做 $1$ 串，用颜色 $1$ 的团子 $2$ 个和颜色 $2$ 的团子 $1$ 个做 $1$ 串，用颜色 $2$ 的团子 $3$ 个做 $1$ 串，共制作 $3$ 串串团子。不能制作超过 $3$ 串，因此输出 $3$。 该样例满足小子任务 $2, 6$ 的约束。 ## 样例解释 4 该样例满足小子任务 $5, 6$ 的约束。 ## 样例解释 5 该样例满足小子任务 $1, 2, 3, 5, 6$ 的约束。 ## 数据范围 - $1 \leq N \leq 200\,000$。 - $0 \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - 所有输入值均为整数。 由 ChatGPT 5 翻译