解题思路

先把题意做一个等价转化。

设原数组为 $a_1,a_2,\dots,a_n$，一个子数组合法，当且仅当这个子数组中任意相邻元素的差的绝对值都不超过 $k$。

对于相邻的两个位置 $i,i+1$，定义一条“边权”：

题目内容

给定一个由$n$个整数构成的数组{$a_1,a_2...，a_n$}；对于每个整数$k(1≤k≤n)$，当且仅当子数组中任意相邻元素的差值的绝对值不超过$k$时，该子数组被称为合法子数组:请计算对于每个$k$，数组中合法子数组的最大长度

【名词解释】得到的新数组。

子数组:从原数组中，连续的选择一段元素(可以全选、可以不选)

输入描述

每个测试文件均包含多组测试数据：

1. 第一行输入一个整数 $T (1≤T≤10^4)$，表示测试数据组数；

2. 接下来对于每组测试数据，依次输入：

   • 第一行输入一个整数 $n (1≤n≤2×10^5)$，表示数组长度；
   • 第二行输入 $n$ 个整数 $a_1,a_2,…,a_n (1≤a_i≤n)$，表示数组元素；

3. 此外，保证所有测试数据中 $n$的总和不超过$2×10^5$。

输出描述

对于每组测试数据，输出一行包含 n 个整数，第 i 个整数表示当 k=i 时合法子数组的最大长度。

样例1

输入

1
5
1 3 5 2 4

输出

1 3 5 5 5