3159: maxD

给定一个长度为 n 的非负整数序列 A 

将 A 划分成 $\lceil \frac{n}{k} \rceil$段，第 i 段为 $A_{k(i-1)+1}，A_{k(i-1)+2}......A_{min(k*i,n)}$

定义 $d_i$ 为第 i 段元素的最大值与最小值的差

$D=max( {d_1,d_2,d_3......d_{\lceil \frac{n}{k} \rceil}} )$

对于所有的 $1\le k\le n$，求 $D$

第一行为一个整数 n。$2\le n \le 10^6$

第二行为 $n$ 个整数，用空格分开，表示序列 $A$ 
$0\le A_i\le 1e9$

输出共一行，一共 $n$ 个数字

第 $i$ 个数字表示 $k=i$ 时的 $D$。

13
1 1 4 5 1 4 1 9 1 9 8 1 0

0 8 8 8 8 8 9 9 9 8 8 8 9