该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

给定一个长度为 $n$ 的排列 $p$（包含 $1 \sim n$ 的每个整数恰好一次）。对于每个 $k = 1, 2, \dots, n-1$，请统计 $p$ 的所有子数组中有多少个是 $k$ 精致序列。

定义：

• 子数组：数组中一段连续的元素，长度至少为 1；
• $k$ 精致序列：长度至少为 2，且任意相邻两项的绝对差不小于 $k$。

输入格式

$t$
$n_1$
$p_{1,1}, p_{1,2} \dots p_{1,n_1}$
$\vdots$
$n_t$
$p_{t,1}, p_{t,2} \dots p_{t,n_t}$

输出格式

对于每个测试用例，输出 $n-1$ 个整数，第 $k$ 个表示该用例中 $k$ 精致子数组的数量。每个测试用例的输出占一行，相邻数之间以一个空格分隔，末尾可留空格。

数据范围

• $1 \le t \le 25000$
• $2 \le n \le 10^5$
• $p$ 是 $1 \sim n$ 的排列
• 所有测试用例的 $n$ 之和不超过 $2 \times 10^5$

样例

输入

3
5
5 1 4 2 3
3
3 2 1
4
3 1 2 4

输出

10 6 3 1
3 0
6 2 0