#P17939. Judgment of Mahou Shoujo

Judgment of Mahou Shoujo

Judgment of Mahou Shoujo

有 nn 名魔法少女围成一圈,按顺时针编号为 1,2,…,n1,2,\ldots,n。其中一部分实际上是魔女。

接下来的 n−3n-3 天,每天依次发生以下事件:

  1. 夜里,恰好一名仍然活着的魔女醒来,杀死其左侧或右侧第一名仍然活着的人。死者也可能是魔女。
  2. 早晨,大家发现当天的死者。

已知每天死者的编号。对每一个早晨,仅依据截至该天的死亡记录,求最初可能存在的魔女的最少数量。不同天的答案可以由不同的最初身份安排实现。

输入格式

第一行是测试用例数 tt,1≤t≤1051\le t\le10^5。

每组用例第一行包含整数 nn。第二行包含 n−3n-3 个两两不同的整数 p1,…,pn−3p_1,\ldots,p_{n-3},pip_i 是第 ii 天死者的编号。

4≤n≤2×1054\le n\le2\times10^5,1≤pi≤n1\le p_i\le n;所有用例的 ∑n≤106\sum n\le10^6。

输出格式

每组用例输出一行 n−3n-3 个整数,第 ii 个是获知前 ii 天死亡记录后的答案。

样例 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。中文整理保留原题的输入输出要求与限制。