rt.

描述

给定 $n$ 个正整数 ${a_n}$ ，你需要将其划分成 $k$ 个连续的段，定义一个段 $[l,r]$ 的权值为: $\text{val}(l,r)=\text{max}_{i=l}^{r}a_i - \text{min}_{i=l}^{r}a_i$

你需要对于每一个 $k=1,2\cdots,n$ 将 $a_n$ 划分成 $k$ 段使得权值和最大，并将最大的权值和输出。

输入

第一行给定一个整数 $n$ 。

第二行给定 $n$ 个正整数 $a_i$ 。

输出

输出共 $n$ 行，其中第 $i$ 行表示 $k=i$ 时的答案。

提示

$1\le n\le 10^4,1\le a_i\le10^5$