CF1923D.Slimes

There are $n$ slimes placed in a line. The slimes are numbered from $1$ to $n$ in order from left to right. The size of the $i$-th slime is $a_i$.

Every second, the following happens: exactly one slime eats one of its neighbors and increases its size by the eaten neighbor's size. A slime can eat its neighbor only if it is strictly bigger than this neighbor. If there is no slime which is strictly bigger than one of its neighbors, the process ends.

For example, suppose $n = 5$, $a = [2, 2, 3, 1, 4]$. The process can go as follows:

• first, the $3$-rd slime eats the $2$-nd slime. The size of the $3$-rd slime becomes $5$, the $2$-nd slime is eaten.
• then, the $3$-rd slime eats the $1$-st slime (they are neighbors since the $2$-nd slime is already eaten). The size of the $3$-rd slime becomes $7$, the $1$-st slime is eaten.
• then, the $5$-th slime eats the $4$-th slime. The size of the $5$-th slime becomes $5$, the $4$-th slime is eaten.
• then, the $3$-rd slime eats the $5$-th slime (they are neighbors since the $4$-th slime is already eaten). The size of the $3$-rd slime becomes $12$, the $5$-th slime is eaten.

For each slime, calculate the minimum number of seconds it takes for this slime to be eaten by another slime (among all possible ways the process can go), or report that it is impossible.

有 $n$ 个史莱姆排成一行。这些史莱姆从左到右依次编号为 $1$ 到 $n$。第 $i$ 个史莱姆的大小为 $a_i$。

每一秒，以下事件恰好发生一次：恰好一个史莱姆吃掉它的一个相邻史莱姆，并将其自身大小增加被吃掉邻居的大小。一个史莱姆仅当其大小严格大于某个相邻史莱姆时，才能吃掉该邻居。若不存在任何一个史莱姆严格大于其任一相邻史莱姆，则该过程终止。

例如，设 $n = 5$，$a = [2, 2, 3, 1, 4]$，则该过程可能如下进行：

• 首先，第 $3$ 个史莱姆吃掉第 $2$ 个史莱姆。第 $3$ 个史莱姆的大小变为 $5$，第 $2$ 个史莱姆被吃掉。
• 接着，第 $3$ 个史莱姆吃掉第 $1$ 个史莱姆（此时它们是相邻的，因为第 $2$ 个史莱姆已被吃掉）。第 $3$ 个史莱姆的大小变为 $7$，第 $1$ 个史莱姆被吃掉。
• 然后，第 $5$ 个史莱姆吃掉第 $4$ 个史莱姆。第 $5$ 个史莱姆的大小变为 $5$，第 $4$ 个史莱姆被吃掉。
• 最后，第 $3$ 个史莱姆吃掉第 $5$ 个史莱姆（此时它们是相邻的，因为第 $4$ 个史莱姆已被吃掉）。第 $3$ 个史莱姆的大小变为 $12$，第 $5$ 个史莱姆被吃掉。

对每个史莱姆，请计算它被另一个史莱姆吃掉所需的最少秒数（在所有可能的过程路径中），若不可能被吃掉，则报告为不可能。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of slimes.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）—— 黏液的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

所有测试用例的 $n$ 值之和不超过 $3 \cdot 10^5$。

For each test case, print $n$ integers. The $i$-th integer should be equal to the minimum number of seconds it takes for the $i$-th slime to be eaten by another slime or -1 if it is impossible.

对于每个测试用例，输出 $n$ 个整数。其中第 $i$ 个整数应等于第 $i$ 个史莱姆被另一个史莱姆吃掉所需的最少秒数；若不可能，则为 $-1$。