Informatica Online Judge

  수열 2 [1636 / 0664]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 5   Total Tried : 6


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[Baltic Olympiad in Informatics 2004 (Ventspils, Latvia)]

Background

수열 A1, A2 .. AN 이 주어졌을 때. 당신은 B1 < B2 < ... < BN 을 만족하면서, |B1 - A1| + |B2 - A2| ... |BN - AN| 을 최소화하는 수열 B를 찾아야 한다.

Input

첫번째 줄에 N이 주어진다.

이후 N개의 줄에 수열 A의 원소가 순서대로 주어진다.

[입력값의 정의역]
수열 1에서, N <= 300, 0 <= Ai <= 100.
수열 2에서, N <= 300, 0 <= Ai <= 2 * 10^9.
수열 3에서, N <= 5000, 0 <= Ai <= 2 * 10^9.
수열 4에서, N <= 100000, 0 <= Ai <= 2 * 10^9.
수열 5에서, N <= 1000000, 0 <= Ai <= 2 * 10^9.

Output

가능한 |B1 - A1| + |B2 - A2| ... |BN - AN| 값의 최소를 출력한다.

IO Example

입력
7
9
4
8
20
14
15
18

출력
13

설명
B = {6,7,8,13,14,15,18} 수열이 |B1 - A1| + |B2 - A2| ... |BN - AN| 값을 최소화한다. 최소화된 값은 13이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]