Removal of a Permutation
Contest: Kotlin Heroes: Episode 11
Tags: *special

You are given a permutation $$$p$$$ of length $$$n$$$.

You can perform operations of two types:

- mark all positions $$$i$$$ such that $$$1 \le i < n$$$ and $$$p_i < p_{i + 1}$$$, and simultaneously remove the elements at these positions;
- mark all positions $$$i$$$ such that $$$2 \le i \le n$$$ and $$$p_{i - 1} > p_i$$$, and simultaneously remove the elements at these positions.

For each integer from $$$1$$$ to $$$(n-1)$$$, calculate the minimum number of operations required to remove that integer from the permutation.

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$$$ ($$$2 \le n \le 250\,000$$$).

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). The array $$$p$$$ is a permutation.

Additional constraints on the input: the sum of $$$n$$$ over all test cases does not exceed $$$250\,000$$$.

Output format:
For each test case, print $$$(n-1)$$$ integers. The $$$i$$$-th of them should be equal to the minimum number of operations required to remove $$$i$$$ from the permutation.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

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

Example output:
1 1 2
1
1 1 2 1 3
1 1 1 2 1 2
1 1 2 1

Editorial:
Consider each pair of adjacent elements. Either $$$p_i < p_{i+1}$$$ (and then an operation of first type "triggers" this pair, deleting the lesser element from it), or $$$p_i > p_{i+1}$$$ (and then an operation of second type "triggers" this pair). So, if we denote the number of elements deleted by the first operation as $$$x$$$ and the number of elements deleted by the second operation as $$$y$$$, then $$$x + y = n - 1$$$. This means that $$$\max(x, y) \ge \frac{n-1}{2}$$$.
If every time we choose an operation which deletes more elements, we will make about $$$\log_2 n$$$ operations in total. So, the answer is bounded by something like $$$18$$$. However, this way to delete everything might not be the fastest for all elements.
Let's iterate on the sequence of operations we make: it must be a sequence of at most $$$\log_2 n$$$ operations, so there are $$$O(n)$$$ such sequences and each of them is analyzed in $$$O(n \log n)$$$. Looks like $$$O(n^2 \log n)$$$, right?
Here comes the magic: if you consider all these sequences of operations not longer than $$$18$$$ recursively, with a function like rec(step, p) (where $$$step$$$ is the current recursion depth, and $$$p$$$ is the current state of the array), it works in $$$O(n \log n)$$$. Why? Obviously, one operation is made in $$$O(m)$$$, where $$$m$$$ is the current size of the array $$$p$$$. However, we can bound the total size of all arrays $$$p$$$ on a single recursion level as $$$O(n)$$$ as follows.
Recall that if we denote the number of elements deleted by the first operation as $$$x$$$ and the number of elements deleted by the second operation as $$$y$$$, then $$$x + y = n - 1$$$ (where $$$n$$$ is the current size of the array). This means that if we ignore one element from each array, then we can think in similar style to "every element appears on each recursion level exactly once" (this is not exactly right, but works very similarly). If you want a more formal proof, then we can say that the total size of all calls on depth $$$x$$$ is equal to the total size of all calls on depth $$$x-1$$$, plus the number of calls on depth $$$x-1$$$. So, on level $$$0$$$, there is one call and total size of calls is $$$n$$$; on level $$$1$$$, there are two calls and the total size of calls is $$$n+1$$$, and so on — on level $$$\log_2 n$$$, we get $$$2^{\log_2 n}$$$ calls with total size of $$$O(n)$$$.
Shortly, the solution can be boiled down to something like "make a recursive search over all sequences of operations, limit the recursion depth by $$$\log_2 n$$$, and it works in $$$O(n \log n)$$$".