J. Joystick Jumping
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Westin the sheep is playing a parkour game.

In the game, there are $$$n$$$ buildings in a line, conveniently numbered $$$1$$$ through $$$n$$$. The $$$i$$$-th building has height $$$h_i$$$. Westin spawns at building $$$s$$$, and his goal is to visit every building at least once.

Westin has an energy level, which is initially a non-negative integer $$$m$$$. In one move, he can jump from a building to an adjacent building. Jumping to a taller adjacent building costs $$$1$$$ unit of energy, so you cannot jump to a taller adjacent building if your energy level is $$$0$$$. Note that jumping to an adjacent building that is the same height or shorter height does not cost any energy, and is always allowed.

Finally, there are two teleporters in the game  — one to the left of building $$$1$$$, and one to the right of building $$$n$$$. Both of these teleporters are on the ground, so you can jump onto them for no energy cost, as long as you are on either building $$$1$$$ or building $$$n$$$. Jumping on either teleporter takes you to the spawnpoint $$$s$$$, and restores your energy level to the original value, $$$m$$$.

A illustration of the optimal strategy in the last sample test. We first jump all the way to the left teleporter, then all the way to building $$$n$$$.

Now you know all the rules of the game. There's just one thing you don't know  — where will Westin spawn? Solve the following problem for each $$$1 \leq s \leq n$$$:

  • Suppose Westin spawns at building $$$s$$$. What's the minimum amount of energy he must start with if he wants to visit every building at least once?
Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \leq t \leq 10^4$$$).

The first line of each test contains $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$, the heights of the buildings ($$$1 \leq h_i \leq 10^9$$$).

It is guaranteed the sum of $$$n$$$ across all tests does not exceed $$$10^5$$$.

Output

In each test, output $$$n$$$ integers. The $$$i$$$-th integer is the minimum energy you need to start with to be able to visit every building at least once, assuming you spawn at building $$$i$$$.

Example
Input
5
5
1 1 1 1 1
4
1 2 3 4
5
1000000000 2 1 2 3
1
999
6
1 6 3 4 5 2
Output
0 0 0 0 0
3 2 1 0
2 2 2 2 2
0
3 2 2 1 1 2
Note

In the first test, all buildings are equal height, so you can jump from any building to any adjacent building with $$$0$$$ cost.

In the second test, the optimal strategy from building $$$3$$$ is to use $$$1$$$ energy to jump to building $$$4$$$, then jump to building $$$3$$$, then jump to building $$$2$$$, then jump to building $$$1$$$. In total we use $$$1$$$ energy. Note, in particular, we don't need to end up at the same building as we start at.