단조수열 만들기

음이 아닌 정수로 이루어진 길이 $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$