logo AlgoBeat OnlineJudge
登录 注册

#216820. [蓝桥杯 2026 国 Python B] 小球消除

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

个小球排成一排,每个小球都有一种颜色。第 个小球的颜色用正整数 表示,颜色编号满足

在游戏过程中,你可以在当前序列的任意位置插入若干个小球,插入的小球颜色也必须在 之间。你也可以反复执行如下消除操作:选择当前序列中连续的三个小球,如果第一个小球和第三个小球颜色相同,就可以将这三个小球同时删除。删除后,左右两侧剩余小球会重新相邻。插入操作和消除操作可以按任意顺序交替进行。

例如,对于颜色序列 ,可以选择前三个小球 并将它们删除,剩余序列为

请你计算,至少需要插入多少个小球,才能使整个序列最终被全部消除。

输入格式

第一行包含一个整数 ,表示测试用例组数。

对于每组测试用例:

  • 第一行包含两个整数 ,分别表示初始小球数量和颜色种类数。
  • 第二行包含 个整数 ,表示初始序列中每个小球的颜色。

输出格式

对于每组测试用例,输出一行,一个整数,表示最少需要插入的小球数量。

样例

样例输入 1

3
4 2
1 2 1 2
5 3
1 2 3 2 1
3 3
1 2 3

样例输出 1

2
1
3

数据范围与提示

【样例说明】

第一组数据中,可以插入两个颜色为 的小球,使序列变为 。先删除前三个小球 ,再删除剩余的 ,即可全部消除。因此答案为

第二组数据中,可以先删除中间的 ,剩下 。再插入一个颜色为 的小球,得到 并将其删除。因此答案为

第三组数据中,至少需要插入 个小球。例如,先插入两个颜色为 的小球形成 并删除,剩余 ;再插入一个颜色为 的小球形成 并删除。

【评测用例规模与约定】

对于 的评测用例,

对于所有评测用例,