순열로 고치기

$N$ 개의 정수로 이루어진 수열 $A$가 있다. 이 수열을 $1, 2, \ldots, N$의 순열로 바꾸고 싶다. 즉, $1$부터 $N$까지의 수가 정확히 한번씩 등장하는 수열로 바꾸려는 것이다. 초기 수열에는 $N$보다 큰 값이 등장할 수 있음에 유의하라.

이 목표를 위해 할 수 있는 작업은 임의의 위치의 값을 임의의 정수로 바꾸는 것이다. 단, $i$ 번째 값을 바꾸는 경우의 비용은 $i$이다.

주어진 수열을 $1, 2, \ldots, N$의 순열로 바꾸는 데 필요한 최소 비용을 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 수열의 크기를 나타내는 정수 $N$이 주어진다. ($1 \le N \le 100\,000$)

그다음 줄에 수열의 정보를 나타내는 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 1\,000\,000\,000$)

출력 형식

첫 줄에 주어진 수열을 $1, 2, \ldots, N$의 순열로 바꾸는 데 필요한 최소 비용을 출력한다.

예제

4
2 1 5 5

7

예제 설명

수열의 세 번째와 네 번째 값을 각각 $3$과 $4$로 바꾸면 된다. 이때, 비용은 $3+4=7$이다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설