Bad-Looking Subsegments

题目描述

Ostad gave Nostad an array $a$ of length $n$ as a birthday gift. However, Nostad thinks that the array is not beautiful because it contains too many bad-looking subsegments.

Nostad considers a subsegment

$$[a_l, a_{l+1}, \cdots, a_r]$$

to be bad-looking if it satisfies at least one of the following conditions:

1. $a_l \le a_{l+1} \le \cdots \le a_r$, i.e., the subsegment is a non-decreasing sequence.
2. $a_l \ge a_{l+1} \ge \cdots \ge a_r$, i.e., the subsegment is a non-increasing sequence.

Nostad plans to remove the elements of the array one by one until the array contains exactly one element. In each operation, he chooses one element of the current array, removes it, and then concatenates the remaining parts.

Before performing any removal and after each removal operation, Nostad computes the length of the longest bad-looking subsegment of the current array and writes it down. As a result, after the array is reduced to a single element, he obtains a sequence

$$l = l_1, l_2, \cdots, l_n,$$

where $l_1$ denotes the length of the longest bad-looking subsegment of the initial array, and for each $i \ge 2$, $l_i$ denotes the length of the longest bad-looking subsegment after the $(i-1)$-th removal.

Since Nostad wants to make the array beautiful as fast as possible, he wants to choose the order of deletions such that the sequence $l$ is lexicographically minimum.

Your task is to compute the lexicographically minimum possible sequence $l$.

输入格式

The first line contains an integer $t$ $(1 \le t \le 10^4)$, the number of test cases.

For each test case:

• The first line contains an integer $n$ $(2 \le n \le 10^6)$, the length of the array.
• The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ $(1 \le a_i \le 10^9)$, representing the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

输出格式

For each test case, print a single line containing $n$ integers

$$l_1, l_2, \cdots, l_n,$$

where $l$ is the lexicographically minimum sequence of longest bad-looking subsegment lengths that Nostad can obtain for that test case.

样例输入 #1

4
7
1 2 3 4 3 2 1
6
2 7 4 3 7 7
5
5 4 3 2 1
5
1 2 3 4 5

样例输出 #1

4 4 3 3 2 2 1 
3 3 2 2 2 1 
5 4 3 2 1 
5 4 3 2 1