CF2011G Removal of a Permutation

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.

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 $ .

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.