소 정렬

면접 대비

시간 제한1초메모리 제한128 MB

요약

두 원소를 교환할 때 두 값의 합만큼 비용이 드는 연산으로 순열을 오름차순으로 정렬할 때 최소 총비용을 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 수학, 구현
정답자: 아직 제출이 없습니다

문제

농부 John의 소 $N$ 마리( $1 \le N \le 10{,}000$ )가 저녁 착유를 위해 한 줄로 서 있습니다. 각 소는 $1$ 부터 $100{,}000$ 사이의 서로 다른 까칠함(grumpiness) 수치를 하나씩 가집니다. 까칠한 소일수록 착유 장비를 망가뜨리기 쉽기 때문에, John은 소들을 까칠함이 증가하는 순서로 다시 세우려고 합니다.

이 과정에서 임의의 두 소(서로 인접하지 않아도 됩니다)의 자리를 맞바꿀 수 있습니다. 까칠한 소일수록 옮기기 어렵기 때문에, 까칠함이 각각 $X$ 와 $Y$ 인 두 소의 자리를 맞바꾸는 데에는 총 $X + Y$ 의 시간이 걸립니다.

소들을 까칠함이 증가하는 순서로 다시 세우는 데 필요한 최소 시간을 구하세요.

입력

첫째 줄: 정수 $N$ .
둘째 줄부터 $N+1$ 째 줄까지: $i+1$ 째 줄에는 $i$ 번째 소의 까칠함 수치가 하나씩 주어집니다.

출력

소들을 까칠함이 증가하는 순서로 다시 세우는 데 필요한 최소 시간을 한 줄에 출력합니다.

힌트

예를 들어 소들이 까칠함 순서로 $2\ 3\ 1$ 과 같이 서 있다고 합시다. 먼저 까칠함이 $3$ 인 소와 $1$ 인 소의 자리를 맞바꾸면 비용은 $3 + 1 = 4$ 이고 순서는 $2\ 1\ 3$ 이 됩니다. 이어서 까칠함이 $1$ 인 소와 $2$ 인 소의 자리를 맞바꾸면 비용은 $1 + 2 = 3$ 이고 순서는 $1\ 2\ 3$ 이 되어, 총 비용은 $7$ 입니다.

예제4

예제 1
입력
```
3
2
3
1
```
예상 출력
```
7
```
예제 2
입력
```
1
5
```
예상 출력
```
0
```
예제 3
입력
```
2
2
1
```
예상 출력
```
3
```
예제 4
입력
```
5
1
2
3
4
5
```
예상 출력
```
0
```