AT_joi2026_semifinal_a 座席 3 (Seats 3)

有 $2N+2$ 个座位排成一排。第 $i$ 个座位（$1 \leq i \leq 2N+2$）的“座位舒适度”为 $A_i$。 现在有 $N$ 组两人结伴而来的顾客，以及 2 位单独前来的 VIP 顾客，需要将这 $2N+2$ 位客人每人分配一个座位。注意，不能有 2 人或以上被分配到同一个座位。 对于每一组两人结伴的顾客，必须被分配到相邻的座位。此时，希望使得分配给 2 位 VIP 顾客的 2 个座位的舒适度总和尽可能大。 给定每个座位的相关信息，请编写程序，求分配给 2 位 VIP 顾客的 2 个座位的舒适度总和的最大值。 ---

输入通过标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $\cdots$ $A_{2N+2}$

输出一个整数，表示分配给 2 位 VIP 顾客的 2 个座位的舒适度总和的最大值。 ---

## 子任务 1. （10 分）$N=1$。 2. （10 分）$N \leq 2$。 3. （10 分）$N \leq 3$。 4. （30 分）$N \leq 2000$。 5. （40 分）没有额外约束。 --- ## 样例解释 1 如下面的分配方式，分配给 2 位 VIP 顾客的座位舒适度总和为 $90$： - 第 1 组顾客分配第 1、2 个座位； - 第 2 组顾客分配第 4、5 个座位； - 2 位 VIP 顾客分配第 3、6 个座位。 无法让 2 位 VIP 顾客的座位舒适度总和超过 $90$，因此输出 $90$。 该样例符合子任务 $2,3,4,5$ 的限制。 --- ## 样例解释 2 本样例满足所有子任务的限制。 --- ## 样例解释 3 本样例满足子任务 $4,5$ 的限制。 # 数据范围 - $1 \leq N \leq 200\,000$。 - $1 \leq A_i \leq 10^9$（$1 \leq i \leq 2N+2$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译