시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB72021617736.270%

문제

음이 아닌 정수로 이루어진 수열 $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_1≤B_2≤\dots ≤B_N$을 만족하거나 $B_1≥B_2≥\dots ≥B_N$를 만족하는 수열을 말한다.

입력

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

출력

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

제한

  • $1≤N≤2\,000$
  • $0≤A_i≤1\,000\,000\,000$

예제 입력 1

7
1
3
2
4
5
3
9

예제 출력 1

3

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO February 2008 Contest > Gold 1번