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

$2N+2$ 個の座席が横一列に並んでいる．左から $i$ 番目の座席 ($1 \le i \le 2N+2$) の座り心地は $A_i$ である． $2$ 人組で訪れたグループ客が $N$ 組と，単身で訪れた VIP 客 $2$ 人がおり，これら $2N+2$ 人の客に $1$ 人 $1$ 個の座席を割り当てる．ただし，$2$ 人以上の客に同じ座席を割り当ててはいけない． いま，同じグループに属する $2$ 人には隣り合う座席を割り当てる必要がある．このとき，VIP 客 $2$ 人に割り当てる $2$ 個の座席の座り心地の合計をなるべく大きくしたい． 座席の情報が与えられたとき，VIP 客 $2$ 人に割り当てる $2$ 個の座席の座り心地の合計の最大値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． $N$ $A_1\ A_2\ \cdots\ A_{2N+2}$

標準出力に，VIP 客 $2$ 人に割り当てる $2$ 個の座席の座り心地の合計の最大値を $1$ 行で出力せよ．

### Sample Explanation 1 以下のように割り当てることで，VIP 客 $2$ 人の座席の座り心地の合計は $90$ になる． - 1 組目のグループには左から $1, 2$ 番目の座席を割り当てる． - 2 組目のグループには左から $4, 5$ 番目の座席を割り当てる． - VIP 客 $2$ 人には左から $3, 6$ 番目の座席を割り当てる． VIP 客 $2$ 人の座席の座り心地の合計を $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$ 点$) $追加の制約はない．