[agc017_c]Snuke and Spells
问题陈述
有 个球排成一行。初始时，从左边开始的第 个球上写着整数 。
当 Snuke 施放一个咒语后，会发生以下情况：
- 假设当前有 个球。所有上面写着 的球会同时消失。
Snuke 的目标是通过多次施放咒语使所有的球都消失。但这可能无法实现。如果无法实现，他希望修改尽量少的球上的整数，使得目标能够实现。
顺便说一下，这些球上的整数有时会自己发生变化。会有 次这样的变化。在第 次变化中，从左边开始的第 个球上的整数会变为 。
每次变化之后，找出 Snuke 必须进行的整数修改次数的最小值，以便在下一次变化发生之前实现他的目标。我们假设他在修改整数方面足够快。请注意，他实际上并不执行这些必要的修改，而是保持它们原样。
约束条件
评分
- 在价值为 分的测试集中， 且 。
输入
输入以以下格式从标准输入给出：
... :
输出
输出 行。第 行应该包含使得 Snuke 的目标能够实现所需的整数修改次数的最小值。
示例输入 1
5 3
1 1 3 4 5
1 2
2 5
5 4
示例输出 1
0
1
1
- 第一次变化之后，球上的整数变为从左到右依次为 、、、、。在这种情况下，通过施放咒语五次可以使所有的球消失。因此，不需要进行任何修改。
- 第二次变化之后，球上的整数变为从左到右依次为 、、、、。在这种情况下，至少需要进行一次修改。一个最优解是将第五个球上的整数修改为 ，然后施放咒语四次。
- 第三次变化之后，球上的整数变为从左到右依次为 、、、、。在这种情况下，至少需要进行一次修改。一个最优解是将第三个球上的整数修改为 ，然后施放咒语三次。
示例输入 2
4 4
4 4 4 4
4 1
3 1
1 1
2 1
示例输出 2
0
1
2
3
示例输入 3
10 10
8 7 2 9 10 6 6 5 5 4
8 1
6 3
6 2
7 10
9 7
9 9
2 4
8 1
1 8
7 7
示例输出 3
1
0
1
2
2
3
3
3
3
2