解题思路
先把题意做一个等价转化。
设原数组为 a1,a2,…,an，一个子数组合法，当且仅当这个子数组中任意相邻元素的差的绝对值都不超过 k。
对于相邻的两个位置 i,i+1，定义一条“边权”：
P4679.第3题-弦上生花
题目内容
给定一个由n个整数构成的数组{a1,a2...，an}；对于每个整数k(1≤k≤n)，当且仅当子数组中任意相邻元素的差值的绝对值不超过k时，该子数组被称为合法子数组:请计算对于每个k，数组中合法子数组的最大长度
【名词解释】得到的新数组。
子数组:从原数组中，连续的选择一段元素(可以全选、可以不选)
输入描述
每个测试文件均包含多组测试数据：
-
第一行输入一个整数 T(1≤T≤104)，表示测试数据组数；
-
接下来对于每组测试数据，依次输入：
- 第一行输入一个整数 n(1≤n≤2×105)，表示数组长度；
- 第二行输入 n 个整数 a1,a2,…,an(1≤ai≤n)，表示数组元素；
-
此外，保证所有测试数据中 n的总和不超过2×105。
输出描述
对于每组测试数据，输出一行包含 n 个整数，第 i 个整数表示当 k=i 时合法子数组的最大长度。
样例1
输入
1
5
1 3 5 2 4
输出
1 3 5 5 5
