#P17939. Judgment of Mahou Shoujo
Judgment of Mahou Shoujo
Judgment of Mahou Shoujo
有 名魔法少女围成一圈,按顺时针编号为 。其中一部分实际上是魔女。
接下来的 天,每天依次发生以下事件:
- 夜里,恰好一名仍然活着的魔女醒来,杀死其左侧或右侧第一名仍然活着的人。死者也可能是魔女。
- 早晨,大家发现当天的死者。
已知每天死者的编号。对每一个早晨,仅依据截至该天的死亡记录,求最初可能存在的魔女的最少数量。不同天的答案可以由不同的最初身份安排实现。
输入格式
第一行是测试用例数 ,。
每组用例第一行包含整数 。第二行包含 个两两不同的整数 , 是第 天死者的编号。
,;所有用例的 。
输出格式
每组用例输出一行 个整数,第 个是获知前 天死亡记录后的答案。
样例 1
5
5
1 2
6
2 1 3
9
1 2 3 4 5 6
10
1 3 5 7 9 2 4
10
2 5 1 8 10 9 4
1 1
1 1 2
1 1 1 1 1 1
1 1 2 2 3 3 3
1 2 2 3 3 3 3
来源
The 4th Universal Cup. Stage 26: Grand Prix of Guangdong — D。中文整理保留原题的输入输出要求与限制。