← 返回题目列表

Codeforces · 1490/D

D. 排列变换

中文机器翻译题面 查看原题

排列 — 是从 $$$1$$$ 到 $$$n$$$ 的长度为 $$$n$$$ 的整数序列,其中所有数字恰好出现一次。例如,$$$[1]$$$、$$$[3, 5, 2, 1, 4]$$$、$$$[1, 3, 2]$$$ — 排列,以及 $$$[2, 3, 2]$$$、$$$[4, 3, 1]$$$、$$$[0]$$$ — 否。

Polycarp 最近被赋予了长度为 $$$n$$$ 的排列 $$$a[1 \dots n]$$$。 Polycarp 更喜欢树而不是排列,因此他想将排列 $$$a$$$ 转换为有根二叉树。他将不同整数的数组转换为树,如下所示:

- 数组的最大元素成为树的根;
- 最大值左侧的所有元素 — 形成左子树(根据相同的规则构建,但应用于数组的左侧部分),但如果最大值左侧没有元素,则根没有左子树;
- 最大值右侧的所有元素 — 形成右子树(根据相同的规则构建,但应用于数组的右侧),但如果最大值右侧没有元素,则根没有右子树。

例如,如果他通过排列 $$$a=[3, 5, 2, 1, 4]$$$ 构建一棵树,那么根将是元素 $$$a_2=5$$$,左子树将是为子数组 $$$a[1 \dots 1] = [3]$$$ 构建的树,而右子树将是为子数组构建的树$$$a[3 \点 5] = [2, 1, 4]$$$。结果,将构建以下树:

对应于排列 $$$a=[3, 5, 2, 1, 4]$$$ 的树。

另一个例子:令排列为$$$a=[1, 3, 2, 7, 5, 6, 4]$$$。在这种情况下,树看起来像这样:

对应于排列 $$$a=[1, 3, 2, 7, 5, 6, 4]$$$ 的树。

让我们用 $$$d_v$$$ 表示顶点 $$$a_v$$$ 的深度,即从根到编号为 $$$a_v$$$ 的顶点的路径上的边数。请注意,根深度为零。给定排列 $$$a$$$,对于每个顶点,找到 $$$d_v$$$ 的值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 排列的长度。

后面跟着 $$$n$$$ 数字 $$$a_1, a_2, \ldots, a_n$$$ — 排列 $$$a$$$。

输出

对于每个测试用例,输出 $$$n$$$ 值 — $$$d_1, d_2, \ldots, d_n$$$。

示例

输入 #1

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

输出 #1

1 0 2 3 1 
0 
0 1 3 2