Feeding Frenzy - Repovive Starter Round 8 | Repovive

23F. Feeding Frenzy

3000 pts2s256 MB

There are $n$ fish in a line, with weights $a_1, a_2, \ldots, a_n$ from left to right.

You choose one fish and give it a non-negative integer amount $x$ of food, increasing its weight by $x$ . After that, only the chosen fish can eat other fish.

In one step, the chosen fish may eat either of its current immediate neighbors, provided that its own weight is at least the weight of that neighbor. The eaten fish is removed from the line, and its weight is added to the chosen fish's weight. The relative order of the remaining fish does not change.

For every $i$ from $1$ to $n$ , find the minimum value of $x$ that allows fish $i$ to eat all the other fish.

The answers are independent: each time, you start with the original line and original weights.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

The first line contains the number of test cases $t$ .

For each test case, the first line contains $n$ . The second line contains $a_1, a_2, \ldots, a_n$ , the initial weights of the fish from left to right.

Output

\left. \begin{array}{l} x_1 \quad x_2 \quad \ldots \quad x_n \end{array} \right\} \times t

For each test case, print one line containing $n$ integers. The value $x_i$ must be the minimum amount of food needed when fish $i$ is chosen.

Samples

Input

Case 1

5
2 1 7 3 2

Case 2

1
9

Explanation

Case 1

If fish $1$ receives $4$ units of food, its weight becomes $6$ . It can eat the fish with initial weights $1$ , $7$ , $3$ , and $2$ , in that order. With less food, its weight after eating the fish of weight $1$ would be less than $7$ , so it would be stuck.

Fish $3$ needs no food. Fish $4$ can receive $2$ units, eat fish $5$ to reach weight $7$ , and then eat all fish to its left.

Case 2

There are no other fish to eat, so no extra food is needed.

Output

Case 1

4 4 0 2 2

Case 2

Input

Case 1

4
5 5 5 5

Case 2

5
10 1 1 1 10

Case 3

3
1 2 4

Explanation

Case 1

Any chosen fish can immediately eat an adjacent fish of equal weight. After that, it is heavy enough to eat every remaining fish.

Case 2

Either fish of weight $10$ can eat all the others without extra food. A fish of weight $1$ can receive $7$ units of food and eat the other two fish of weight $1$ , reaching weight $10$ . It can then eat both remaining fish. With less than $7$ units, even after eating both other small fish, it is too light to eat either fish of weight $10$ .

Case 3

Fish $1$ can receive $1$ unit of food and eat fish $2$ , reaching weight $4$ , before eating fish $3$ . Without food, it cannot make its first move.

Fish $2$ can receive $1$ unit and eat fish $1$ , reaching weight $4$ . Without food, it can only eat fish $1$ and then gets stuck at weight $3$ .

Fish $3$ can eat both other fish without extra food.

Output

Case 1

0 0 0 0

Case 2

0 7 7 7 0

Case 3

1 1 0

There are $n$ fish in a line, with weights $a_1, a_2, \ldots, a_n$ from left to right.

You choose one fish and give it a non-negative integer amount $x$ of food, increasing its weight by $x$ . After that, only the chosen fish can eat other fish.

For every $i$ from $1$ to $n$ , find the minimum value of $x$ that allows fish $i$ to eat all the other fish.

The answers are independent: each time, you start with the original line and original weights.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array} \right\} \times t

The first line contains the number of test cases $t$ .

For each test case, the first line contains $n$ . The second line contains $a_1, a_2, \ldots, a_n$ , the initial weights of the fish from left to right.

\left. \begin{array}{l} x_1 \quad x_2 \quad \ldots \quad x_n \end{array} \right\} \times t

For each test case, print one line containing $n$ integers. The value $x_i$ must be the minimum amount of food needed when fish $i$ is chosen.

Fish $3$ needs no food. Fish $4$ can receive $2$ units, eat fish $5$ to reach weight $7$ , and then eat all fish to its left.

Fish $1$ can receive $1$ unit of food and eat fish $2$ , reaching weight $4$ , before eating fish $3$ . Without food, it cannot make its first move.

Fish $2$ can receive $1$ unit and eat fish $1$ , reaching weight $4$ . Without food, it can only eat fish $1$ and then gets stuck at weight $3$ .

Fish $3$ can eat both other fish without extra food.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

23F. Feeding Frenzy

Constraints

Input

Output

Samples

23F. Feeding Frenzy

Constraints

Input

Output

Samples