G. The Elden Program
time limit per test
1 с
memory limit per test
1024 megabytes
input
standard input
output
standard output

Zack is a professional gamer who loves to play challenging games. Recently, he has been playing a very difficult game called The Elden Program. In The Elden Program, there are $$$n$$$ monsters standing in a row, where each monster $$$i$$$ has an energy level of $$$a_i$$$.

Fortunately, Zack found a powerful spell that he can use against the monsters. This spell can be cast on a single monster. When he casts this spell on a monster $$$x$$$, monster $$$x$$$ becomes fixed in place, while every other monster will:

  • Pick a direction, either to the left or to the right, and never change it.
  • Start moving in the chosen direction simultaneously, each second moving to an adjacent index. Each move takes one unit of time.
  • If two different monsters $$$i$$$ and $$$j$$$ encounter each other, and $$$a_i \: \gt \: a_j$$$, then monster $$$i$$$ will defeat monster $$$j$$$ and the energy of monster $$$i$$$ will increase by $$$a_j$$$.
  • If two different monsters $$$i$$$ and $$$j$$$ encounter each other, and $$$a_i \: = \: a_j$$$, then both monsters will vanish.

Keep in mind that when a monster vanishes, that doesn't mean they are defeated.

The rest of the monsters perform those actions in such a way to minimize the time it takes to defeat monster $$$x$$$.

Zack wants to plan out his assault on the monsters, so he asks you to determine the time it takes to defeat each monster if the spell was cast on it, or determine that it's impossible to defeat it.

Input

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

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

The second line of each testcase consists of $$$n$$$ integers $$$(1 \le a_i \le 10^9)$$$ — denoting the energy of each monster.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each testcase, output $$$n$$$ numbers, the time it takes to defeat monster $$$i$$$ if the spell was cast on it, or "-1" if it is impossible to defeat it.

Example
Input
6
12
5 6 3 1 5 5 5 8 1 6 7 6
12
5 6 3 1 5 5 5 8 1 6 1 5
12
5 6 3 1 5 5 5 100 1 6 1 5
12
5 6 3 1 5 5 5 8 1 6 7 6
5
1 1 1 1 1
5
10 1 1 1 2
Output
1 3 1 1 3 2 1 3 1 1 3 1 
1 3 1 1 3 2 1 6 1 2 1 2 
1 3 1 1 3 2 1 -1 1 2 1 2 
1 3 1 1 3 2 1 3 1 1 3 1 
-1 -1 -1 -1 -1 
-1 1 2 1 4
Note

Consider the second testcase. When you cast a spell on the $$$8$$$-th monster $$$a_8 = 8$$$, all the other monsters will work together to defeat it. The monsters on the right of the $$$8$$$-th monster will go to the right so they won't increase it's power. The 2-nd monster $$$a_2 = 6$$$ will go towards the $$$8$$$-th monster while the other monsters in between the two monsters will go into the $$$2$$$-nd monster increasing it's power.