题目描述

南派北派武林大会开始了。本次攻擂赛有 $n$ 名武者参加，其中按顺序第 $i$ 名武者获得战斗力属性为 $i$ 。每名武者分来自南派或者北派。如果不同派系的武者在擂台上相遇，战斗力属性值大的获得胜利，如果同派系的武者在擂台上相遇，强者会相让弱者，战斗力属性值小的会获得胜利。参加战斗的所有武者两两都会进行一场决斗，请你计算出每名武者获胜的次数。

输入描述

单个测试用例包含多组数据

输入第一行为一个整数 $T$ ，表示有 $T$组测试样例。

对于每一组数据，包含两行数据，第一行是人数 $n$

输入第二行为$n$ 个数 $a_{i}$ 表示派系所属 ($a_i$ 只会取 $0$ 或 $1$)，$0$ 表示来自南派， $1$表示来自北派

数字间两两空格隔开

1 $\leq$ $T$ $\leq$ $5$ , $n$ $\leq$ $50000$ , $0$ $\leq$ $a_i$ $\leq$ $1$

输出描述

对于每组数据，输出一行，包括 $n$ 个整数，每个整数表示每个人能赢多少场。

样例

输入

3
9
0 0 1 0 0 1 0 0 1
6
1 1 0 1 1 0
4
1 0 0 0

输出

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

题目思路

思路：模拟 + 前缀和

按照题意模拟，从小到大存储每个阵营的数。

对于每个数 $x$，计算自己阵营中大于 $x$ 的数，以及敌方阵营中小于 $x$ 的数。

可以用一个前缀和维护两个阵营中小于 $x$ 的数的个数。