Description

Jack got a new video game called “Rounding,” which contains $n$ levels. The game features a global ranking system that ranks all players worldwide based on their scores. Jack wants to break the global record and let everyone know who the master of this game is, so he has investigated the scoring system extensively.

He finally understands the scoring rules: when a player finishes each level, they earn some points. The player’s score is the average points they earn per level, rounded to the nearest whole number. More precisely, if a player plays a total of $k$ levels and earns $p_1, p_2, \dots, p_k$ points respectively, their score will be $\lfloor \frac{\sum_{i=1}^k p_i}{k} + 0.5 \rfloor$. For example, if a player earns [2,3,3] points in 3 levels, their score will be $\lfloor \frac{2+3+3}{3} + 0.5 \rfloor = 3$.

Jack has practiced several times and knows the points $a_i$ he will earn in the $i$-th level. He discovered an exploit in the game that allows him to skip some levels at the beginning and stop at any time. This means Jack can choose a pair of numbers $(l,r)$ where $1 \le l \le r \le n$, and only play the levels from $l$ to $r$.

Jack is curious about the maximum score he can achieve for each starting level $l$ for $1 \le l \le n$, and how many levels he should play to achieve that maximum score. If there are several answers that yield the maximum score, he should print the smallest number of levels, as playing the game for a long time is unhealthy.

Input Format

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

Output Format

For each test case, output $n$ integers in one line. The $i$-th number indicates the number of levels Jack should play, starting from level $i$, to achieve the maximum score. If there are several answers that achieve the maximum score, print the smallest number of levels.

3
3
1 3 3
4
1 2 3 4
5
2 3 2 3 3

2 1 1
4 2 2 1
2 1 2 1 1

Hint

• $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$'s of all test cases is at most $2 \times 10^5$.