Codeforces Round 914 (Div. 2) |
---|
Finished |
You are given an array a of n positive integers and a score. If your score is greater than or equal to ai, then you can increase your score by ai and remove ai from the array.
For each index i, output the maximum number of additional array elements that you can remove if you remove ai and then set your score to ai. Note that the removal of ai should not be counted in the answer.
Each test contains multiple test cases. The first line contains an integer t (1≤t≤5000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤105) — the length of the array.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the elements of the array.
It is guaranteed that the sum of n over all test cases does not exceed 105.
For each test case, output n integers, the i-th of which denotes the maximum number of additional array elements that you can remove if you remove ai from the array and then set your score to ai.
4520 5 1 4 231434 7 1442115999999999 999999999 999999999 1000000000 1000000000
4 3 0 3 1 1 0 2 0 4 4 4 4 4
In the first test case, the answers are as follows:
If we start with i=4, our initial score is a4=4 and a=[20,5,1,2]. We can remove 3 additional elements in the following order:
If we start with i=1 we can remove all remaining elements in the array, so the answer is 4.
If we start with i=2, we can remove 3 additional elements in the following order: 1, 4, 2.
If we start with i=3, we can remove no additional elements.
If we start with i=5, we can remove 1 additional element: 1.
Name |
---|