题目内容

在序列分析中，我们常需找出波动幅度不超过特定阈值的连续区段。给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$，定义相邻位置的“绝对差” $d_i = |a_i - a_{i+1}|$（$1 \le i < n$）。对于一个给定的整数 $k$，若一个连续子序列 $a_l, a_{l+1}, \dots, a_r$ 满足其内部所有相邻绝对差均不超过 $k$，即 $\max_{l \le i < r} d_i \le k$，则称该子序列是 $k$-平稳的。注意：单个元素本身总是 $k$-平稳的。请对于每一个 $k = 1, 2, \dots, n$，计算序列中最长 $k$-平稳连续子序列的长度。

数据范围：

• 测试数据组数 $T$ 满足 $1 \le T \le 10^4$。
• 每组数据中序列长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，所有测试数据的 $n$ 总和不超过 $2 \times 10^5$。
• 序列元素 $a_i$ 均为整数，且 $1 \le a_i \le n$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来依次描述每组测试数据，每组数据占两行：第一行包含一个整数 $n$，表示序列长度；第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列中的元素。

输出描述

对于每组测试数据，输出一行，包含 $n$ 个整数，其中第 $i$ 个整数表示当 $k = i$ 时的最长 $k$-平稳连续子序列的长度。

样例1

输入

1
3
1 2 1

输出

3 3 3

说明

序列长度为 3，元素为 1 2 1。相邻绝对差：$d_1=|1-2|=1$，$d_2=|2-1|=1$。对于 $k=1$，所有边权 $d_i \le 1$，因此并查集将位置 1、2、3 合并为一个连通块，大小为 3。由于 $k$ 增大不会删除边，$k=2$ 和 $k=3$ 时最大连通块仍为 3。故输出 3 3 3。

样例2

输入

1
5
1 1 3 3 1

输出

2 5 5 5 5

说明

序列长度为 5，元素为 1 1 3 3 1。相邻绝对差：$d_1=|1-1|=0$，$d_2=|1-3|=2$，$d_3=|3-3|=0$，$d_4=|3-1|=2$。边权从小到大排序为 $(0,1\text{-}2)$，$(0,3\text{-}4)$，$(2,2\text{-}3)$，$(2,4\text{-}5)$。

当 $k=1$ 时，加入边权为 0 的两条边：位置 1–2 连通（大小 2），位置 3–4 连通（大小 2）。最大连通块为 2。

当 $k=2$ 时，继续加入边权为 2 的两条边：2–3 和 4–5。此时 1–2–3–4–5 全部连通，大小为 5。$k=2,3,4,5$ 的答案均为 5。故输出 2 5 5 5 5。

样例3

输入

1
1
5

输出

1

说明

序列长度为 1，元素为 5。没有相邻边。对于任意 $k$，最长平稳子序列的长度为单个元素本身，即 1。因此输出 1。

样例4

输入

1
6
1 2 4 4 3 6

输出

3 5 6 6 6 6

说明

序列长度为 6，元素为 1 2 4 4 3 6。相邻绝对差：$d_1=|1-2|=1$，$d_2=|2-4|=2$，$d_3=|4-4|=0$，$d_4=|4-3|=1$，$d_5=|3-6|=3$。边权排序：$(0,3\text{-}4)$，$(1,1\text{-}2)$，$(1,4\text{-}5)$，$(2,2\text{-}3)$，$(3,5\text{-}6)$。

• $k=1$：加入边权 $0$ 和两个 $1$。连接 1–2（大小 2），3–4–5（大小 3），最大 3。
• $k=2$：加入边权 $2$ 的边（2–3）。1–2–3–4–5 连通，大小 5。
• $k=3$：加入边权 $3$ 的边（5–6），全连通，大小 6。
• $k \ge 4$ 时答案保持 6。故输出 3 5 6 6 6 6。