{"problem":{"name":"[COCI 2023/2024 #2] Kuglice","description":{"content":"一个双端队列里面有 $n$ 个球，每个球有一个颜色。A 和 B 玩一个游戏： A 先手，两个人轮流操作，每次从队列的最左端或者最右端拿出一个球，如果这种颜色的球是第一次被拿出，拿出它的人获得 $1$ 分。所有球都拿完后游戏结束。 假设 A 和 B 都以最优策略操作，请求出最终得分是多少。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9911"},"statements":[{"statement_type":"Markdown","content":"一个双端队列里面有 $n$ 个球，每个球有一个颜色。A 和 B 玩一个游戏：\n\nA 先手，两个人轮流操作，每次从队列的最左端或者最右端拿出一个球，如果这种颜色的球是第一次被拿出，拿出它的人获得 $1$ 分。所有球都拿完后游戏结束。\n\n假设 A 和 B 都以最优策略操作，请求出最终得分是多少。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行 $n$ 个整数 $a_{1\\sim n}$ 表示从左到右每个球的颜色。\n\n## Output\n\n输出一行两个以 `:` 隔开的整数（形如 `a:b`），`a` 表示 A 最终的得分，`b` 表示 B 最终的得分。\n\n[samples]\n\n## Note\n\n### 数据范围\n|$\\text{Subtask}$|分值|特殊性质|\n|:-:|:-:|:-:|\n|$1$|$17$|$a_i\\le 2$|\n|$2$|$10$|$n\\le 20$|\n|$3$|$26$|$a_i\\le 20$|\n|$4$|$15$|$n\\le 300$|\n|$5$|$42$|无|\n\n对于所有数据，$1\\le n\\le 3000$，$1\\le a_i\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9911","tags":["2023","O2优化","COCI（克罗地亚）"],"sample_group":[["5\n1 1 2 1 1","1:1"],["6\n1 2 3 1 2 3","2:1"]],"created_at":"2026-03-03 11:09:25"}}