座席3 (Seats 3)

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

• 1 ≦N ≦200 000.
• 1 ≦Ai ≦109 (1 ≦i ≦2N + 2).
• 入力される値はすべて整数である.

The 25^th Japanese Olympiad in Informatics (JOI 2025/2026)
Semifinal Stage
February 1, 2026 (Shimbashi, Tokyo)

1. (10 点) N = 1.
2. (10 点) N ≦2.
3. (10 点) N ≦3.
4. (30 点) N ≦2 000.
5. (40 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N
A1 A2 · · · A2N+2

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

생성자가 기록되지 않았습니다.

출처 JOI 2026 Semifinal