Elections
Contest: Codeforces Round 953 (Div. 2)
Difficulty rating: 1600
Tags: data structures, greedy, implementation, math

Elections are taking place in Berland. There are $$$n$$$ candidates participating in the elections, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th candidate has $$$a_i$$$ fans who will vote for him. Additionally, there are $$$c$$$ people who are undecided about their favorite candidate, let's call them undecided. Undecided people will vote for the candidate with the lowest number.

The candidate who receives the maximum number of votes wins the elections, and if multiple candidates receive the same maximum number of votes, the candidate with the lowest number among them wins.

You found these elections too boring and predictable, so you decided to exclude some candidates from them. If you do not allow candidate number $$$i$$$ to participate in the elections, all $$$a_i$$$ of his fans will become undecided, and will vote for the candidate with the lowest number.

You are curious to find, for each $$$i$$$ from $$$1$$$ to $$$n$$$, the minimum number of candidates that need to be excluded from the elections for candidate number $$$i$$$ to win the elections.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le c \le 10^9$$$) — the number of candidates in the elections and the number of undecided people.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the number of fans for each candidate.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$n$$$ integers, the $$$i$$$-th of which should be equal to the minimum number of candidates that need to be excluded from the elections for candidate number $$$i$$$ to win.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

- If all candidates are allowed, candidate number $$$1$$$ will receive $$$3$$$ votes ($$$1$$$ undecided person will vote for him), candidate number $$$2$$$ will receive $$$0$$$ votes, and candidate number $$$3$$$ will receive $$$3$$$ votes. Therefore, candidate number $$$1$$$ wins (he received the same number of votes as candidate $$$3$$$, but his number is lower), so the answer for him is $$$0$$$.
- If candidate number $$$1$$$ is not allowed, his $$$2$$$ fans will become undecided. Then candidate number $$$2$$$ will receive $$$3$$$ votes ($$$3$$$ undecided people will vote for him) and candidate number $$$3$$$ will receive $$$3$$$ votes. Therefore, candidate number $$$2$$$ wins (he received the same number of votes as candidate $$$3$$$, but his number is lower), so the answer for him is $$$1$$$.
- If candidates with numbers $$$1$$$ and $$$2$$$ are not allowed, candidate number $$$3$$$ wins, so the answer for him is $$$2$$$.

In the second test case, candidate number $$$1$$$ will win if candidate number $$$2$$$ is not allowed to participate.

Example input:
5
3 1
2 0 3
2 3
0 10
5 3
5 4 3 2 1
4 5
3 10 7 1
6 0
2 2 2 3 3 3

Example output:
0 1 2
1 0
0 1 2 3 4
1 0 2 3
1 1 2 0 4 5

Editorial:
Notice that if candidate $$$i$$$ does not win initially (when no one is removed), then for their victory, we must definitely remove all candidates with numbers less than $$$i$$$. Because if someone remains unremoved with a number less than $$$i$$$, then the votes for candidate $$$i$$$ will not increase, and the maximum number of votes for someone else will not decrease.
Let's find the winner of the election initially, for them the answer is $$$0$$$, for all other candidates we need to remove all people with numbers less than $$$i$$$.
But sometimes these removals alone may not be enough, so we need to additionally remove several candidates so that their fans' votes go to us.
Notice that then it is enough to remove only one candidate with the maximum $$$a_i$$$, then we will definitely win, so the answer for candidate $$$i$$$ is either $$$0$$$, or $$$i$$$, or $$$i + 1$$$.
So we end up with a solution which works in $$$O(n)$$$.