logo Algo Beat Contest
登录 注册

#10006. [CF1453F] 更难的益智游戏

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

卡评测将会被封号。

Gildong 现在正在开发一款益智游戏。该游戏包含 个编号为 的平台。玩家在游戏中扮演一个角色,可以站在每个平台上,目标是将角色从第 个平台移动到第 个平台。

个平台上标有一个整数 )。当角色站在第 个平台时,玩家可以将角色移动到任意 号平台,其中 。如果角色站在 的平台上,玩家就会输掉游戏。

由于 Gildong 认为当前的游戏难度还不够,他想让游戏变得更难。他希望将一些(可能为零个)平台的标签改为 ,使得仅剩下唯一一条获胜路径。他希望对游戏的修改尽可能少,因此请你帮他计算,最少需要将多少个平台的标签改为 ,才能使仅剩下唯一一条获胜方式。两种方式不同,当且仅当存在某个平台在其中一种方式中到达,而在另一种方式中没有到达。

输入格式

每组测试数据包含一个或多个测试用例。第一行为测试用例个数 )。

每个测试用例包含两行。第一行为一个整数 ),表示游戏的平台数量。

第二行为 个整数,第 个整数为 ),表示第 个平台上的整数。

保证:

  • 对于每个测试用例,初始时至少存在一条获胜路径。
  • 所有测试用例中 的总和不超过

输出格式

对于每个测试用例,输出一个整数,表示最少需要将多少个平台的标签改为 ,才能使仅剩下一条获胜方式。

样例

输入 #1

3
4
1 1 1 0
5
4 3 2 1 0
9
4 1 4 2 1 0 2 1 0

输出 #1

0
3
2

数据范围与提示

在第一个样例中,玩家只能依次移动到下一个平台,直到到达第 个平台。由于已经只有一条获胜路径,答案为

在第二个样例中,Gildong 可以将 改为 ,使得游戏变为 。此时玩家唯一的获胜方式是直接从第 个平台跳到第 个平台。

在第三个样例中,Gildong 可以将 改为 ,此时唯一的获胜路径为: