수중 정원

다오는 게임의 대규모 패치를 준비하고 있다. 대규모 패치의 내용은 수중 정원의 오픈으로, 수중 정원은 아름다운 해저의 모습을 볼 수 있는 여러 맵으로 이루어질 예정이다.

이미 수중 정원 전체의 디자인은 모두 완성되었다. 일직선 형태로 쭉 이어진 형태의 수중 정원은 수심이 계속 변화하는 형태로 다양한 바다 풍경을 유저에게 제공한다. 이에 따라, 수중 정원에서 각 맵의 매력도는 그 맵에서 가장 깊은 수심과 가장 얕은 수심의 차이로 정의된다. 이 값이 클수록 더 다양한 풍경을 볼 수 있기 때문이다. 다오는 수심에 대한 정보가 $N$ 개 있는 수중 정원을 $K$ 개의 맵으로 분할하여 모든 맵의 매력도의 합을 최대화하고자 한다.

다오는 다음과 같이 문제를 추상화하였다. 수중 정원 전체를 맨 왼쪽에서부터 쭉 보았을 때 각 지역의 수심을 나열하여 크기 $N$인 정수 수열로 볼 수 있을 것이다. 이 수열을 $H = H_1, H_2, .., H_N$ 이라고 하자. 이때, 이 수열을 연속한 구간 $K$ 개로 나누어 각 구간 내에서 최댓값과 최솟값의 차이들의 합을 최대화하는 것이 다오의 목적이다.

예를 들어, $N = 5$, $K = 2$, $H = [2, 4, 1, 4, 3]$ 인 경우를 생각해보자. 맵을 $[2, 4, 1], [4, 3]$의 둘로 나누었다면 두 맵의 매력도는 각각 $3, 1$ 이 되어 그 합이 $4$가 된다. 한편, 맵을 $[2, 4], [1, 4, 3]$의 둘로 나눈 경우 두 맵의 매력도는 $2, 3$ 이 되어 그 합이 $5$이다. 매력도의 합이 $5$보다 커지도록 두 맵으로 나누는 것은 불가능하므로 $5$가 매력도의 합의 최댓값이다.

맵의 개수는 다오가 혼자서 정할 수 없기 때문에, 다오는 가능한 모든 $K$에 대해서 수중 정원을 $K$ 개의 맵으로 나눌 때 매력도 합의 최댓값을 구해놓고자 한다. 다오를 도와 $K = 1, 2, .., N$인 $N$ 가지 경우에 대해 매력도 합의 최댓값을 구하여라.

입력 형식

첫 줄에 수중 정원의 크기 $N$이 주어진다. $(1 \le N \le 200\,000)$

둘째 줄에 수중 정원에 대한 정보를 나타내는 $N$ 개의 정수 $H_1, H_2, .., H_N$가 공백으로 구분되어 주어진다. $(1 \le H_i \le 10^9)$

출력 형식

$N$ 개의 줄에 걸쳐 답을 출력한다. $i$ 번째 줄에 수중 정원을 $i$ 개의 맵으로 나누는 경우 매력도 총합의 최댓값을 출력한다.

예제

5
2 4 1 4 3

3
5
5
3
0

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설