구간 나누기

$N$개의 수 $A\_1, A\_2, \cdots , A\_N$이 주어진다. 이 때 서로 겹치지 않는 연속한 구간을 정확히 $K$개를 잡아 각 구간 점수의 합을 구했을 때, 가능한 값의 최댓값을 구하는 프로그램을 작성하라.

이 문제에서 어떤 구간의 점수는 구간에 속한 수의 최댓값과 최솟값의 차이와 같다.

문제를 정확하게 정의하면 다음과 같다.

다음을 만족하는 $2K$개의 정수 $s\_1, e\_1, s\_2, e\_2, \cdots , s\_K, e\_K$ ($1 ≤ s_1 ≤ e_1 < s_2 ≤ e_2 < \cdots ≤ s_K ≤ e_K ≤ N)에 대해 다음을 최대화하라.

$\sum\_{k=1}^{K}{p(s\_k,e\_k)}$

단,

$p(s, e) = \max{(A\_s, \cdots, A\_e)} - \min{(A\_s, \cdots, A\_e)}$

첫 번째 줄에 두 정수 $N$ ($1 ≤ N ≤ 2 \times 10^5$)과 $R$ ($1 ≤ R ≤ \min{(200, N)}$)가 공백으로 구분되어 주어진다. 당신의 프로그램은 $1 ≤ K ≤ R$ 범위의 모든 $K$에 대한 답을 출력해야 한다.

두 번째 줄에 $N$개의 정수 $A\_1, A\_2, \cdots , A\_N$ ($1 ≤ A\_i ≤ 10^9$)이 순서대로 공백으로 구분되어 주어진다. 이 중 $i$번째로 주어지는 수가 $A\_i$이다.

총 $R$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $K = i$일 때의 답을 출력한다. 즉, $A$에서 서로 겹치지 않는 연속한 구간을 정확히 $i$개를 잡아 각 구간 점수의 합을 구했을 때 가능한 값의 최댓값을 출력한다.

$K = 1$: [2, 3]의 한 구간을 잡으면 최적이다.

$K = 2$: [1, 2], [4, 5]의 두 구간을 잡으면 최적이다.

$K = 3$: [1, 2], [3, 4], [5, 6]의 세 구간을 잡으면 최적이다.