多测试生成器

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

若数组 $b_1,b_2,\ldots,b_m$ 满足 $b_1=m-1$，则称它是一个 test。

若 $b_2,b_3,\ldots,b_m$ 可以被划分成恰好 $b_1$ 个非空连续子数组，且每个子数组都是 test，则称整个数组是一个 multitest。每个元素必须恰好属于一个子数组。

一次操作可以把任意一个元素替换为任意非负整数。记 $f(b)$ 为把数组 $b$ 变成 multitest 的最少操作数。

给定正整数数组 $a_1,a_2,\ldots,a_n$。对每个 $1\le i<n$，求 $f([a_i,a_{i+1},\ldots,a_n])$。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行一个整数 $n$，第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组测试数据输出一行 $n-1$ 个整数，依次为所有要求的后缀答案。

样例输入 1

3
4
1 2 1 7
7
3 1 3 1 2 1 1
4
2 7 1 1

样例输出 1

0 1 1
0 1 1 0 1 1
1 1 1

样例输入 2

1
19
3 4 1 2 1 7 7 3 1 3 1 2 1 1 4 2 7 1 1

样例输出 2

0 0 1 1 1 1 1 1 1 0 1 0 1 0 2 1 1 1

数据范围

• $1\le t\le300000$；
• $2\le n\le300000$；
• $1\le a_i\le300000$；
• 所有测试数据的 $n$ 之和不超过 $300000$。