소 정렬

농부 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$입니다.