금고 열기
시간 제한1초메모리 제한128 MB
10,000,000칸짜리 원형 트랙 위의 N개 위치를 한 점으로 모으는 데 필요한 최소 이동 거리 합을 구하는 문제입니다.
문제
미르코는 작은 금고를 열려고 한다. 금고의 잠금장치는 완전히 똑같은 N개의 원판으로 이루어져 있다. 각 원판은 크기가 같은 10,000,000개의 조각으로 나뉘어 있고, 조각에는 시계 방향으로 1부터 10,000,000까지 번호가 매겨져 있다. 처음에는 서로 다른 원판에서 같은 번호를 가진 조각들이 정확히 위아래로 겹쳐져 있다.
각 원판에는 조각이 정확히 하나 빠져 있으며, 이 빠진 조각을 구멍이라고 부른다.
금고를 열려면 모든 구멍이 같은 번호의 위치에 오도록, 즉 전부 위아래로 정렬되어야 한다.
1초에 미르코는 원판 하나를 시계 방향 또는 반시계 방향으로 한 조각만큼 돌릴 수 있다. 원판은 원형이므로 1번 조각과 10,000,000번 조각은 서로 이웃한다.
모든 구멍을 정렬하는 데 필요한 최소 시간(초)을 구하여라.
입력
첫째 줄에 원판의 개수 N (2 ≤ N ≤ 100,000)이 주어진다.
다음 N개의 줄에 각 원판에 있는 구멍의 처음 위치가 주어진다. i+1번째 줄에는 i번째 원판의 구멍 위치를 나타내는 정수 P_i (1 ≤ P_i ≤ 10,000,000)가 주어진다.
출력
모든 구멍을 정렬하는 데 필요한 최소 시간(초)을 한 줄에 출력한다.
참고: 답이 매우 커질 수 있으므로 자료형의 범위에 주의하여라(64비트 정수를 사용해야 한다).