有 $n$ 名选手在进行无限制格斗大赛，他们的编号分别为 $1\sim n$。

一开始，这些选手以 $p_1,p_2,\dots,p_n$ 的顺序从左到右排列。接下来，主办方会举行 $n-1$ 次比赛，每次选择剩余选手中相邻的两个。每场比赛会决出一名胜者和败者，败者退出，胜者留在自己原来的位置，保持剩余选手相对顺序不变。容易发现，$n-1$ 次比赛之后会恰好剩下一名选手，他就是此次大赛的冠军。

由于比赛有黑幕，主办方可以任意决定胜者和败者是谁，但是观众对举行的比赛有独特的要求。具体的，设进行比赛的两位相邻选手的编号从左到右是 $x,y$，如果有 $x < y$，那么观众认为这场比赛是合理的，反之是不合理的。注意一场比赛是否合理与谁胜出无关。

现在主办方想要知道，对于每个选手，让他成为冠军最少要举行多少次不合理的比赛。

输入格式

第一行输入数据组数 $T$。

对于每组数据，先输入一行一个正整数 $n$，再输入一行 $n$ 个正整数 $p_1,\dots,p_n$。

输出格式

对于每组数据，输出一行 $n$ 个整数，分别为编号为 $1\sim n$ 的选手的答案。

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

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

对于第一组数据，让 $1$ 胜出时一种最优的举行比赛的方式为：

• $3,4$ 进行合理比赛，$4$ 胜出，剩余选手顺序为 $4,2,1,5$
• $1,5$ 进行合理比赛，$1$ 胜出，剩余选手顺序为 $4,2,1$
• $4,2$ 进行不合理比赛，$2$ 胜出，剩余选手顺序为 $2,1$
• $2,1$ 进行不合理比赛，$1$ 胜出，剩余选手顺序为 $1$

样例二-六

见下发文件。

数据范围

对于全部数据，$\sum n \leq 10^6$，$p$ 是 $1,2,\dots,n$ 的排列。

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$