구간 나누기

$N$개의 수 $A_1, A_2, \cdots, A_N$이 주어진다. 서로 겹치지 않는 연속한 구간을 정확히 $K$개 잡고, 각 구간의 점수를 모두 더했을 때 가능한 값의 최댓값을 구하는 프로그램을 작성하라.

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

정확하게 정의하면 다음과 같다.

다음 조건을 만족하는 $2K$개의 정수 $s_1, e_1, s_2, e_2, \cdots, s_K, e_K$에 대해 아래 값을 최대화하라.

$\sum_{k=1}^{K} p(s_k, e_k)$

여기서

$p(s, e) = \max(A_s, \cdots, A_e) - \min(A_s, \cdots, A_e)$

이고, $1 \le s_1 \le e_1 < s_2 \le e_2 < \cdots \le s_K \le e_K \le N$이다.

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

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$ ($1 \le A_i \le 10^9$)이 순서대로 공백으로 구분되어 주어진다.

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

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

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

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