说明

杰克得到了一款名为“四舍五入”的新电子游戏，该游戏包含 $n$ 个关卡。游戏设有一个全球排名系统，根据玩家的得分对全世界的玩家进行排名。杰克想打破世界纪录，让所有人都知道谁是这款游戏的大师，因此他深入研究了游戏的计分系统。

他终于弄清楚了计分规则：当玩家完成每个关卡时，都会获得一定的分数。玩家的得分是他们在每个关卡中获得分数的平均值，四舍五入到最接近的整数。更准确地说，如果一个玩家总共玩了 $k$ 个关卡，分别获得 $p_1, p_2, \dots, p_k$ 分，那么他的得分为 $\lfloor \frac{\sum_{i=1}^k p_i}{k} + 0.5 \rfloor$。例如，如果一名玩家在 $3$ 个关卡中获得了 $[2,3,3]$ 分，那么他的得分将为 $\lfloor \frac{2+3+3}{3} + 0.5 \rfloor = 3$。

杰克已经练习了很多次，他知道自己在第 $i$ 个关卡中能获得的分数 $a_i$。他发现了游戏中的一个漏洞，允许他跳过开头的若干关卡，并可以在任意时刻停止。这意味着杰克可以选择一对数 $(l, r)$，其中 $1 \le l \le r \le n$，并只玩从第 $l$ 关到第 $r$ 关。

杰克想知道对于每个起始关卡 $l$（$1 \le l \le n$），他所能达到的最高得分，以及为了达到该最高得分他应该玩多少个关卡。如果有多种方案都能达到最高得分，他应输出最少的关卡数，因为长时间玩游戏对健康不利。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。每个测试用例由两行组成。第一行包含一个整数 $n$，表示视频游戏中的关卡数。第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$，表示杰克在每个关卡中获得的分数。

输出格式

对于每个测试用例，在一行中输出 $n$ 个整数。第 $i$ 个整数表示从第 $i$ 关开始玩，为了达到最高得分应玩的关卡数。如果有多种方案能达到最高得分，则输出最少的关卡数。

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

提示

• $1 \le t \le 10^5$
• $1 \le n \le 2 \times 10^5$
• $0 \le a_i \le 10^9$，对于 $i \in \{1, 2, \dots, n\}$
• 所有测试用例的 $n$ 之和不超过 $2 \times 10^5$

翻译由 DeepSeek V3.2 完成