按摩座椅

题目描述:

狐狸尼克的经商头脑很灵活，他看到电影院有很多人等候时没有足够的座椅，于是他抓住了这个商机，在电影院门口投放了很多按摩座椅，供人们使用。

狐狸尼克一共投放 $2n+2$个按摩座椅并排成一行，每个按摩座椅有且只有一个座位。从左数第 $i( 1 \le i \le 2n+2)$个座椅的舒适度为$a_i$。

现有$n$对结伴而来的情侣客人，以及$2$位单身来访的 VIP 客人，狐狸尼克需要为这 $2n+2$位客人每人分配一个座位。但是，不能将同一个座位分配给两位或更多的客人。

现在，对于属于同一对情侣的两个人，必须分配相邻的座位。在此条件下，狐狸尼克希望分配给两位单身来访的 VIP 客人的两个座位的舒适度之和尽可能大。

给定每个按摩座椅的舒适度信息，请编写一个程序，求出尼克分配给两位单身来访的 VIP 客人的两个座位的舒适度之和的最大值。

输入格式:

第一行包含一个整数$n$ 。

第二行包含 $2n+2$个整数，第$i( 1 \le i \le 2n+2)$个整数为 ，表示第$i$个按摩座椅的舒适度。

输出格式:

输出共一行一个整数，即分配给两位单身来访的 VIP 客人的两个座位的舒适度之和的最大值。

数据范围:

对于100%的数据：$1\le n \le 200,000; 1 \le a_i \le 10^9 (1 \le i \le n ) $。

样例输入:

(双击复制)

样例1：
2
20 60 40 30 10 50

样例2：
1
1000000000 1000000000 1 1

样例3：
4
4 10 8 6 7 6 7 8 12 3

样例输出:

(双击复制)

样例1：
90

样例2：
2000000000

样例3：
16

提示:

【样例1解释】

狐狸尼克通过如下分配，可以使得两位单身来访的 VIP 客人的座位舒适度之和达到 90。

为第$1$对情侣分配从左数第$1、2$ 号座位。为第 $2$对情侣分配从左数第$4、5$号座位。为两位单身来访的 VIP 客人分配从左数第$3、6$号座位。这也是最优解，输出$40+50=90$ 。

时间限制: 1000ms
空间限制: 256MB

---

来源: 26年比赛小学组t2