题目思路

思路：模拟 + 前缀和

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

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

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

题目内容

在一场大型编程马拉松中，共有 $n$ 位选手参赛。每位选手按照报名顺序获得一个唯一的编号，即第 $1$ 位报名的选手编号为 $1$，第 $2$ 位编号为 $2$，以此类推直至编号 $n$。每位选手在此之前已被预先分配至红组或蓝组，组别分别用数字 0 和 1 表示。

比赛采用两两对战的完全轮赛制，即任意两名不同选手都会进行一次对决。对决的胜负规则如下：

• 若两名选手来自不同组别，则编号较大的一方获胜；
• 若两名选手来自同一组别，则编号较小的一方获胜。

请为每位选手计算出其在整个轮赛中获胜的总场数。

约束条件：

• 测试用例组数 $T$ 不超过 5；
• 每组选手人数 $n$ 不超过 50000；
• 组别标记仅为 0 或 1。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。 接下来依次给出每组数据： 每组第一行输入一个整数 $n$，表示选手人数； 第二行输入 $n$ 个用空格隔开的整数 $g_1, g_2, \dots, g_n$，其中 $g_i$ 为 0 或 1，表示编号为 $i$ 的选手的组别。

输出描述

对于每组数据，输出一行 $n$ 个用空格分隔的整数，其中第 $i$ 个整数表示编号为 $i$ 的选手获胜的场数。

样例1

输入

1
1
0

输出

0

说明

该组数据只有 $n=1$ 名选手，编号为 1，组别为 0。因为没有其他选手可以与其对决，所以这名选手的获胜场数为 0。

样例2

输入

1
3
0 1 0

输出

1 1 1

说明

共有 $n=3$ 名选手，组别依次为 0、1、0。

• 编号 1（组别 0）与编号 2（组别 1）对决：不同组，编号大者胜，2 获胜；编号 1 与编号 3（组别 0）对决：同组，编号小者胜，1 获胜。因此编号 1 获胜 1 场。
• 编号 2（组别 1）与编号 1 对决：不同组，2 获胜；编号 2 与编号 3 对决：不同组，编号大者胜，3 获胜。因此编号 2 获胜 1 场。
• 编号 3（组别 0）与编号 1 对决：同组，1 获胜；编号 3 与编号 2 对决：不同组，3 获胜。因此编号 3 获胜 1 场。

最终每人获胜 1 场。

样例3

输入

1
4
0 0 0 0

输出

3 2 1 0

说明

共有 $n=4$ 名选手，全部属于 0 组。同组对决时，编号较小的一方获胜。

• 编号 1 与 2、3、4 的对决均因编号更小获胜，共胜 3 场。
• 编号 2 胜 3、4，负于 1，共胜 2 场。
• 编号 3 胜 4，负于 1、2，共胜 1 场。
• 编号 4 负于所有其他选手，共胜 0 场。

输出为 3 2 1 0。

样例4

输入

2
2
0 1
2
1 1

输出

0 1
1 0

说明

共 $T=2$ 组测试数据。

第一组：$n=2$，组别 0 1。编号 1 与 2 不同组，编号大者胜，2 获胜，1 失败。因此 1 胜 0 场，2 胜 1 场，输出 0 1。

第二组：$n=2$，组别 1 1。同组编号小者胜，1 获胜，2 失败。输出 1 0。