24667번 - Tarzan Jumps 다국어

문제

In a forest near Almaty, there are $N$ trees arranged in a row, numbered from 1ドル$ through $N$ from left to right. Tree number $i$ has height $H_i$.

In one jump, Tarzan can move from the top of tree $i$ to the top of tree $j$ ($i < j$) if all the trees between them are either strictly lower or strictly higher than both trees $i$ and $j$. In particular, he can jump from tree $i$ to tree $i + 1$. More formally, the jump is possible if at least one of the following conditions holds:

• $j = i + 1,ドル
• for all $k$ ($i < k < j$): $H_i > H_k$ and $H_j > H_k,ドル
• for all $k$ ($i < k < j$): $H_i < H_k$ and $H_j < H_k$.

Tarzan is currently standing on tree 1ドル,ドル and he wants to reach tree $N$. Tarzan's ICPC teammate, Abay, can help him. Specifically, he can perform the following change any number of times: choose a number $i$ (1ドル \le i \le n$), an integer $x$ (0ドル \le x \le 10^{18}$), and set $H_i = x$.

For each $k$ from 1ドル$ to $N,ドル find the least number of changes that Abay must perform so that Tarzan could get to tree $N$ in no more than $k$ jumps.

입력

The first line contains a single integer $t,ドル the number of test cases (1ドル \le t \le 150,000円$). The description of test cases follows.

The first line of each test case contains an integer $N,ドル the number of trees (2ドル \le N \le 300,000円$).

The second line of each test case contains $N$ integers $H_1, H_2, \ldots, H_N$ (1ドル \le H_i \le 10^9$).

It is guaranteed that the sum of $N$ over all test cases does not exceed 300ドル,000円$.

출력

For each test case, print $N$ integers: for each $k$ from 1ドル$ to $N,ドル print the least number of changes that Abay must perform so that Tarzan could get from tree 1ドル$ to tree $N$ in no more than $k$ jumps.

제한

힌트

In the first test case, for $k = 1,ドル Abay can change the height of tree 1ドル$ to 3ドル,ドル and Tarzan will be able to jump to the last tree. For $k = 2$ and $k = 3,ドル Tarzan can reach the last tree without any changes.