在荒原上建造了许多烽火台。曾经有 $n$ 座烽火台从西向东排列，用于抵御入侵者。根据历史记录，第 $i$ 座烽火台的海拔高度为 $a_i$。

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

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

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示荒原上烽火台的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，按顺序表示烽火台的海拔高度。

输出格式

输出 $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