Game of Rounding

Jack got a new video game called "Rounding" with $n$ levels. The game has a global ranking system that ranks all players worldwide by their scores. Jack wants to break the global record and show everyone he is the master of this game, so he studied the scoring system closely.

He finally understands the scoring rules. Each time a player finishes a level, they earn some points. A player's score is the average points per level, rounded to the nearest whole number. More precisely, if a player plays $k$ levels and earns $p_1, p_2, \dots, p_k$ points, the score is $\left\lfloor \frac{\sum_{i=1}^k{p_i}}{k} + 0.5\right\rfloor$. For example, if a player earns $[2, 3, 3]$ points in 3 levels, the score is $\left\lfloor \frac{2+3+3}{3} + 0.5\right\rfloor = 3$.

Jack has practiced several times and knows the points $a_i$ he will earn in level $i$. He found an exploit that lets him skip some levels at the beginning and stop at any time. So Jack can choose a pair $(l, r)$ with $1 \le l \le r \le n$ and play only levels $l$ through $r$.

For each starting level $l$ with $1 \le l \le n$, Jack wants to know the maximum score he can achieve and how many levels he should play to reach it. If several choices give the maximum score, he should report the smallest number of levels, since playing for a long time is unhealthy.

The first line contains an integer $t$, the number of test cases. Each test case consists of two lines. The first line contains an integer $n$, the number of levels. The second line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$, the points earned in each level.

For each test case, output $n$ integers on one line. The $i$-th number is the number of levels Jack should play, starting from level $i$, to achieve the maximum score. If several choices achieve the maximum score, print the smallest number of levels.

$1 \le t \le 10^5$

$1 \le n \le 2 \times 10^5$

$0 \le a_i \le 10^9$ for $i \in \{1, 2, \dots, n\}$.

The sum of $n$ over all test cases is at most $2 \times 10^5$.