2021.8.5 Permutation Transformation

A permutation — is a sequence of length nn integers from 11 to nn, in which all the numbers occur exactly once. For example, [1], [3,5,2,1,4], [1,3,2] — permutations, and [2,3,2], [4,3,1][4,3,1], [0] — no.

Polycarp was recently gifted a permutation a[1…n] of length n. Polycarp likes trees more than permutations, so he wants to transform permutation aa into a rooted binary tree. He transforms an array of different integers into a tree as follows:

• the maximum element of the array becomes the root of the tree;
• all elements to the left of the maximum — form a left subtree (which is built according to the same rules but applied to the left part of the array), but if there are no elements to the left of the maximum, then the root has no left child;
• all elements to the right of the maximum — form a right subtree (which is built according to the same rules but applied to the right side of the array), but if there are no elements to the right of the maximum, then the root has no right child.

For example, if he builds a tree by permutation a=[3,5,2,1,4], then the root will be the element a2=5, and the left subtree will be the tree that will be built for the subarray a[1…1]=[3], and the right one — for the subarray a[3…5]=[2,1,4]. As a result, the following tree will be built:

 The tree corresponding to the permutation a=[3,5,2,1,4]

Another example: let the permutation be a=[1,3,2,7,5,6,4]. In this case, the tree looks like this:

 The tree corresponding to the permutation a=[1,3,2,7,5,6,4]

Let us denote by dv the depth of the vertex av, that is, the number of edges on the path from the root to the vertex numbered av. Note that the root depth is zero. Given the permutation a, for each vertex, find the value of dv.

Input

The first line contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow.

The first line of each test case contains an integer n (1≤n≤100) — the length of the permutation.

This is followed by n numbers a1,a2,…,an — permutation a.

Output

For each test case, output nn values — d1,d2,…,dn

Example

Input

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

Output

1 0 2 3 1 
0 
0 1 3 2 

此英文题臭长，刚一看题确实吓住了。仔细看树状图，我们很容易想到BFS按层次搜索。

慢慢探索将此题一步一步写出，并一次性通过OJ，这在平生乃是罕事，特作纪念。

#include<bits/stdc++.h>
using namespace std;
int a[105], dv[105];//dv数组用来记录a[]中每个数的层次
int MaxIndex(int i, int j)//返回a[i]....a[j]间最大数的序号
{
	int c = a[i], index = i;
	for (int x = i + 1; x <= j; x++)
	{
		if (c < a[x])
		{
			c = a[x];
			index = x;
		}
	}
	return index;
}
int main(void)
{
	int t;
	cin >> t;
	while (t--)
	{
		memset(dv, 0, sizeof(dv));//由于有多组测试案例，每次需将dv数组重置
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		queue<int> qu;
		qu.push(MaxIndex(1, n));//先找到所有数中的最大值，并置为队首
		dv[qu.front()] = 1;//根部的深度先设为1，代表已经搜索过了，后面判断某个数是不是搜索过了可以直接判断其dv[]是否为0
		while (!qu.empty())
		{
			int ind = qu.front(); qu.pop();//取出队首元素
			int l, r, Left = 0, Right = 0;
			for ( l = ind - 1; l >= 1 ; l--)//查找队首元素左边还没搜索过的元素的最小序号
			{
				if (dv[l] != 0)
				{
					Left = l + 1;
					break;
				}
			}
			if (!Left) Left = 1;//如果Left==0说明队首元素左边的所有元素都没有被搜索过，所以队首元素左边还没搜索过的元素的最小序号为1
			if (Left <= ind - 1)
			{
				int tmp = MaxIndex(Left, ind - 1);//找到队首元素左边元素最大值的序号并压入队列
				dv[tmp] = dv[ind] + 1;//此元素的层次就是父结点+1，这与BFS中步数的记录原理一样
				qu.push(tmp);
			}
			for (r = ind + 1; r <= n; r++)//队首的右边元素同理操作
			{
				if (dv[r] != 0)
				{
					Right = r - 1;
					break;
				}
			}
			if (!Right) Right = n;
			if (Right >= ind + 1)
			{
				int tmp = MaxIndex(ind + 1, Right);
				dv[tmp] = dv[ind] + 1;
				qu.push(tmp);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			cout << dv[i] - 1 << ' ';//因为跟结点的深度为0，所以所有元素的深度要-1
		}
		cout << endl;
	}
	return 0;
}