Slimes
Contest: Educational Codeforces Round 162 (Rated for Div. 2)
Difficulty rating: 1800
Tags: binary search, constructive algorithms, data structures, greedy, two pointers

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.

Input format:
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$$$.

Output format:
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.

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

Example input:
4
4
3 2 4 2
3
1 2 3
5
2 2 3 1 1
7
4 2 3 6 1 1 8

Example output:
2 1 2 1 
1 1 -1 
2 1 -1 1 2 
2 1 1 3 1 1 4

Editorial:
Let's solve the problem independently for each slime (denote it as $$$i$$$).
After any number of seconds, the size of each slime is equal to the sum of some subarray. In order to eat the $$$i$$$-th slime, the "eater" should be its neighbor. So the eater size is equal to the sum of subarray $$$[j, i-1]$$$ for some $$$j < i$$$ or $$$[i + 1, j$$$] for some $$$j > i$$$. It remains to understand which $$$j$$$ can be the answer. First of all, the sum of subarray should be strictly greater than $$$a_i$$$. And also, there should be a sequence of operations that can combine the selected segment of slimes into one slime. Such a sequence exists in two cases:
• the length of subarray is $$$1$$$;
• there are at least two distinct values in subarray.
It is not difficult to prove that these are the only conditions. If the length is $$$1$$$, then the subarray is already just only one slime. If all the slimes have the same size, then none of the neighboring pairs can be combined, which means that it is impossible to combine all slimes into one. If there are at least two distinct values, there exist a pair of adjacent slimes of the form (maximum, not maximum). After combining such a pair, the result is the only maximum of the subarray, which means that it can eat all the other slimes in the subarray.
It remains to understand how to find such $$$j$$$ that satisfies the aforementioned conditions and is as close to $$$i$$$ as possible (because the number of required operations is $$$|i-j|$$$) faster than iterating over all values of $$$j$$$. We can notice that, if the subarray $$$[j, i-1]$$$ is good, then the subarray $$$[j-1, i-1]$$$ is also good. This leads us to the fact that we can use binary search. It is enough to pre-calculate two arrays: an array of prefix sums that used to find the sum of the subarray and an array $$$p$$$, where $$$p_i$$$ is the position of the nearest element that different to $$$a_i$$$ — to determine whether there are two different elements.
So we can find the answer for one slime in $$$O(\log{n})$$$. And the total running time is $$$O(n\log{n})$$$.