烽火台沿长城而建。曾经有 $n$ 座烽火台从西向东排列，用于抵御外敌。根据历史记录，第 $i$ 座烽火台的海拔高度为 $a_i$。

防御者战略性地将所有烽火台划分为 $k$ 个部分，每个部分包含若干座（至少一座）连续的烽火台。一个部分的规模定义为该部分中烽火台最高海拔与最低海拔之差。最合理的划分方式是使得所有部分的规模之和最大。

作为一名历史学家，你非常想知道对于每一个 $k = 1, 2, \dots, n$，规模之和的最大值是多少。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示长城沿线的烽火台数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中第 $i$ 个整数 $a_i$ ($1 \le a_i \le 10^5$) 表示第 $i$ 座烽火台的海拔高度。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数，表示 $k = i$ 时的最大规模之和。

样例

样例输入 1

5
1 2 3 4 5

样例输出 1

4
3
2
1
0

样例输入 2

5
1 2 1 2 1

样例输出 2

1
2
2
1
0