{"problem":{"name":"[NOISG 2024 Prelim] Party","description":{"content":"James 有 $n$ 个朋友，他想选择其中的 $0$ 个或者更多朋友来参加他的聚会。第 $i$ 个朋友如果参加了他的聚会，会产生 $a_i$ 点快乐值。注意：有些朋友并不想参加聚会，所以他们的 $a_i$ 会是负的。 然而，他家只有一排 $n$ 个座位，而且因为社交距离，两个人不能坐在相邻的座位上。现在 James 想知道，如果他按照最优方案邀请朋友，这些朋友的快乐值的和最大为多少。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10709"},"statements":[{"statement_type":"Markdown","content":"James 有 $n$ 个朋友，他想选择其中的 $0$ 个或者更多朋友来参加他的聚会。第 $i$ 个朋友如果参加了他的聚会，会产生 $a_i$ 点快乐值。注意：有些朋友并不想参加聚会，所以他们的 $a_i$ 会是负的。\n\n然而，他家只有一排 $n$ 个座位，而且因为社交距离，两个人不能坐在相邻的座位上。现在 James 想知道，如果他按照最优方案邀请朋友，这些朋友的快乐值的和最大为多少。\n\n## Input\n\n第一行，一个整数 $n$。\n\n第二行 $n$ 个整数，表示 $a$。\n\n## Output\n\n一行一个整数，表示答案。\n\n[samples]\n\n## Background\n\n翻译自 [NOI SG 2024 Prelim B.Party](https://github.com/noisg/noi-2024-prelim)。\n\n## Note\n\n### 【样例 #1 解释】\n\nJames 可以邀请第 $1,4,5$ 位朋友。\n\n### 【样例 #2 解释】\n\nJames 可以邀请唯一一位朋友。\n\n### 【样例 #3 解释】\n\nJames 可以邀请第 $3,4,6$ 位朋友。\n\n### 【数据范围】\n\n|$\\text{Subtask}$|分值|特殊性质|\n|:-:|:-:|:-:|\n|$0$|$0$|样例|\n|$1$|$49$|$n\\le 3$|\n|$2$|$38$|$n\\le 1000$|\n|$3$|$13$|无|\n\n对于 $100\\%$ 的数据，$1 \\le n \\le 2 \\times 10^5,-10^9 \\le a_i \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10709","tags":["数学","贪心","2024","排序","NOISG（新加坡）"],"sample_group":[["5\n3 2 -1 4 5","12"],["1\n10","10"],["6\n1 -3 2 10 -4 9","21"]],"created_at":"2026-03-03 11:09:25"}}