← 返回题目列表

Codeforces · 1904/B

B. 收集游戏

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

给你一个由 $$$n$$$ 正整数组成的数组 $$$a$$$ 和一个分数。如果您的分数大于或等于 $$$a_i$$$,那么您可以将您的分数增加 $$$a_i$$$ 并从数组中删除 $$$a_i$$$。

对于每个索引 $$$i$$$,输出如果删除 $$$a_i$$$ 可以删除的附加数组元素的最大数量,然后将分数设置为 $$$a_i$$$。请注意,删除 $$$a_i$$$ 不应计入答案中。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 表示如果从数组中删除 $$$a_i$$$,然后将分数设置为 $$$a_i$$$,则可以删除的附加数组元素的最大数量。

示例

输入 #1

4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000

输出 #1

4 3 0 3 1 
1 0 2 
0 
4 4 4 4 4

注意

第一个测试用例中,答案如下:

如果我们从 $$$i=4$$$ 开始,我们的初始分数是 $$$a_4=4$$$ 和 $$$a=[20,5,1,2]$$$。我们可以按以下顺序删除 $$$3$$$ 附加元素:

1. 由于 $$$4 \ge 1$$$,我们可以删除 $$$1$$$,我们的分数变为 $$$5$$$。之后,$$$a=[20,5,2]$$$。
2. 由于 $$$5 \ge 5$$$,我们可以删除 $$$5$$$,我们的分数变为 $$$10$$$。之后,$$$a=[20,2]$$$。
3. 由于 $$$10 \ge 2$$$,我们可以删除 $$$2$$$,我们的分数变为 $$$12$$$。之后,$$$a=[20]$$$。

如果我们从 $$$i=1$$$ 开始,我们可以删除数组中所有剩余的元素,所以答案是 $$$4$$$。

如果我们从 $$$i=2$$$ 开始,我们可以按以下顺序删除 $$$3$$$ 附加元素:$$$1$$$、$$$4$$$、$$$2$$$。

如果我们从 $$$i=3$$$ 开始,我们就不能删除任何其他元素。

如果我们从 $$$i=5$$$ 开始,我们可以删除 $$$1$$$ 附加元素:$$$1$$$。