题目内容

小 A 获得了一个特殊的数列，它由 $1$ 到 $n$ 的 $n$ 个整数组成，每个整数恰好出现一次。

对于数列中的某个位置 $i$，考虑所有包含位置 $i$ 的连续子区间。在某个子区间中，设比 $a_i$ 小的元素有 $x$ 个，比 $a_i$ 大的元素有 $y$ 个。如果 $x - y$ 等于 $0$ 或 $1$，就称 $a_i$ 是这个子区间的 均衡值。

请你统计每个位置 $i$ 所对应的元素 $a_i$ 在多少个不同的连续子区间中恰好充当均衡值。

约束条件：

• 测试数据组数 $T$ 满足 $1 \le T \le 10$。
• 数列长度 $n$ 满足 $1 \le n \le 5000$。
• 单个测试文件中所有 $n$ 的总和不超过 $5000$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来依次给出每组数据：

• 第一行包含一个整数 $n$，表示数列的长度。
• 第二行包含 $n$ 个整数，代表数列中的元素。保证这些整数恰好是 $1$ 到 $n$ 的一个排列。

输出描述

对于每组数据，输出一行 $n$ 个整数，用空格分隔。其中第 $i$ 个整数表示位置 $i$ 对应的元素作为均衡值的连续子区间个数。

样例1

输入

1
1
1

输出

1

说明

数列只有一个元素 1。包含位置 1 的连续子区间只有 [1]。

该区间内比 1 小的元素个数 $x = 0$，比 1 大的元素个数 $y = 0$，满足 $x - y = 0$，因此 1 是该区间的均衡值。

位置 1 恰好充当均衡值的子区间个数为 1。

样例2

输入

1
2
2 1

输出

2 1

说明

数列为 [2, 1]。

• 位置 1（元素 2）：包含它的子区间有 [2]（$x=0,\ y=0,\ x-y=0$）和 [2, 1]（比 2 小的有 1 个，即 $x=1$；比 2 大的有 $y=0$，$x-y=1$）。两个区间均满足均衡值条件，故答案为 2。

• 位置 2（元素 1）：包含它的子区间有 [1]（$x=0,\ y=0$）和 [2, 1]（$x=0,\ y=1$，$x-y=-1$）。只有 [1] 满足条件，故答案为 1。

因此输出 2 1。

样例3

输入

2
2
1 2
3
3 1 2

输出

1 2
2 1 3

说明

共有两组测试数据。

第一组数据（$n=2$，排列 1 2）：

• 位置 1（元素 1）：子区间 [1] 满足（$x-y=0$），[1,2] 中 $x=0,\ y=1$，不满足。答案为 1。
• 位置 2（元素 2）：子区间 [2] 满足，[1,2] 中 $x=1,\ y=0$，满足。答案为 2。

第二组数据（$n=3$，排列 3 1 2）：

• 位置 1（元素 3）：子区间 [3]（$x-y=0$）满足；[3,1]（$x=1,\ y=0$）满足；[3,1,2]（$x=2,\ y=0$）不满足。答案为 2。
• 位置 2（元素 1）：子区间 [1] 满足；其余包含 1 的区间比它大的元素更多，$x-y$ 均为负数。答案为 1。
• 位置 3（元素 2）：子区间 [2]（$x-y=0$）满足；[1,2]（$x=1,\ y=0$）满足；[3,1,2]（比 2 小的有 1 个，比 2 大的有 1 个，$x-y=0$）满足。答案为 3。

因此第一行输出 1 2，第二行输出 2 1 3。