P15451 [JOI 2026 SemiFinal] 座位 3 / Seats 3

有 $2N+2$ 个座位排成一行。从左数第 $i$ 个座位 ($1 \le i \le 2N+2$) 的舒适度为 $A_i$。 现有 $N$ 组结伴而来的两人团体客人，以及 $2$ 名单身来访的 VIP 客人，需要为这 $2N+2$ 位客人每人分配一个座位。但是，不能将同一个座位分配给两位或以上的客人。 现在，对于属于同一团体的两个人，必须分配相邻的座位。在此条件下，我们希望分配给两位 VIP 客人的两个座位的舒适度之和尽可能大。 给定座位的相关信息，请编写一个程序，求出分配给两位 VIP 客人的两个座位的舒适度之和的最大值。

输入以下格式从标准输入给出。 $N$ $A_1\ A_2\ \cdots\ A_{2N+2}$

在标准输出中，以一行输出分配给两位 VIP 客人的两个座位的舒适度之和的最大值。

### 样例解释 1 通过如下分配，两位 VIP 客人的座位舒适度之和可以达到 $90$。 - 为第 1 组团体分配从左数第 $1,2$ 号座位。 - 为第 2 组团体分配从左数第 $4,5$ 号座位。 - 为两位 VIP 客人分配从左数第 $3,6$ 号座位。 无法使两位 VIP 客人的座位舒适度之和大于 $90$，因此输出 $90$。 该输入样例满足子任务 $2,3,4,5$ 的数据范围。 ### 数据范围 - $1 \le N \le 200\,000$ - $1 \le A_i \le 10^9$ ($1 \le i \le 2N+2$) - 输入的所有值均为整数。 ### 子任务 1. (10 分) $N = 1$ 2. (10 分) $N \le 2$ 3. (10 分) $N \le 3$ 4. (30 分) $N \le 2000$ 5. (40 分) 无额外限制。 翻译由 DeepSeek 完成