단조수열 만들기

시간 제한2초메모리 제한128 MB

요약

N개의 정수가 주어질 때 원래 수열과의 절대값 차이 합을 최소화하는 단조 수열(비내림 또는 비증가)을 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 힙, 수학
정답자: 아직 제출이 없습니다

문제

음이 아닌 정수로 이루어진 길이 $N$ 의 수열 $A_1, A_2, \dots, A_N$ 이 주어진다. 수열 $B_1, B_2, \dots, B_N$ 을 하나 정해 $|A_1-B_1| + |A_2-B_2| + \dots + |A_N-B_N|$ 의 값을 최소로 하려고 한다.

수열 $B$ 는 단조수열이어야 한다. 즉, $B_1 \le B_2 \le \dots \le B_N$ 을 만족하거나 $B_1 \ge B_2 \ge \dots \ge B_N$ 을 만족해야 한다.

입력

첫째 줄에 수열의 길이 $N$ 이 주어진다. 둘째 줄부터 $N$ 개의 줄에는 $A_1, A_2, \dots, A_N$ 이 순서대로 하나씩 주어진다.

출력

첫째 줄에 가능한 절댓값 합의 최솟값을 출력한다.

제한

$1 \le N \le 2\,000$
$0 \le A_i \le 1\,000\,000\,000$

예제1

예제 1
입력
```
7
1
3
2
4
5
3
9
```
예상 출력
```
3
```