#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

//============================================================================
#define pred(x) ((x)-1)
#define succ(x) ((x)+1)
//============================================================================
typedef unsigned char  INT8U;
typedef unsigned short INT16U;
typedef   signed short INT16S;
typedef long INT32;
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
INT16U *C;
//----------------------------------------------------------------------------
void CountingSort(INT16U *A, INT16U *B,  INT16U n, INT16U k)
{
    long i;

    for (i = 0; i<n; i++)
        C[A[i]]++;
    for (i = 1; i<=k; i++)
        C[i] += C[i-1];
    /*for (i = 1; i<=k; i++)
        printf("%d ", C[i]);
    printf("\n");
    printf("B[C[A[i]]-1] = A[i];\n");
    for (i=n-1; 0<=i; i--){
        B[C[A[i]]-1] = A[i];
        printf("B[%d]=%d C[%d]=%d A[%d]=%d\n", C[A[i]]-1, B[C[A[i]]-1],
                            A[i], C[A[i]], i, A[i]);
        C[A[i]]--;
    }*/
}
//----------------------------------------------------------------------------
INT16S getminptr(INT16U *A, INT16U N)
{
    INT16U i,min; INT16S ptr;

    for (i=0, ptr=-1, min=32767; i<N; i++){
        if (A[i]<min && pred(C[A[i]])!=i){
            min=A[i];
            ptr=i;
        }
    }
    return ptr;
}
//----------------------------------------------------------------------------
long sum;
void exchange(INT16U *x, INT16U *y)
{
    INT16U z;

    z=*x, *x=*y, *y=z;
    sum+=*x;
    sum+=*y;
    //printf("ex: %d<-->%d, sum:%ld\n", *y, *x, sum);
}
//----------------------------------------------------------------------------
long mincostsort(INT16U *A, INT16U N)
{
    int ptr,i,j,min;

    for (i=sum=0; i<pred(N); i++)
    for (j=succ(i); j<N; j++)
        if (pred(C[A[j]])==i && pred(C[A[i]])==j)
            exchange(&A[i], &A[j]);
    for (i=0,j=32000; i<N; i++)
        if (A[i]<j)
            j=A[i],min=i;
    for (; 0<=(ptr=getminptr(A, N));){
        if (A[min]<A[ptr]){
            exchange(&A[min], &A[ptr]);
            //ptr=min;
        }
        while (pred(C[A[ptr]])!=ptr){
            for (i=0; i<N; i++)
                if (C[A[i]]==succ(ptr)){
                    exchange(&A[ptr], &A[i]);
                    ptr=i;
#ifdef DESKTOP
                    for (j=0; j<N; j++)
                        printf("%2d ", A[j]);
                    printf(" sum:%ld\n", sum);
#endif
                    break;
                }
        }
    }
    return sum;
}
//----------------------------------------------------------------------------
/*
*                                         *     *
0 62 33 29 72 52 43 19 5  93 51 32  8 11 56 47 66 69 30 17 68  5
0 62 33 29 72 52 43 19 32 93 51  5  8 11 56 47 66 69 30 17 68  5
0 62 33 29 72 52 43 19 32 93 51 47  8 11 56  5 66 69 30 17 68  5
0  5 33 29 72 52 43 19 32 93 51 47  8 11 56 62 66 69 30 17 68  0
0  5 33 29 72 52 43 19 32 93  8 47 51 11 56 62 66 69 30 17 68  8
0  5 33 29 72 52  8 19 32 93 43 47 51 11 56 62 66 69 30 17 68  8
0  5 33  8 72 52 29 19 32 93 43 47 51 11 56 62 66 69 30 17 68  8
0  5 33 11 72 52 29 19 32 93 43 47 51  8 56 62 66 69 30 17 68  8
0  5 33 11 72  8 29 19 32 93 43 47 51 52 56 62 66 69 30 17 68  8
0  5 33 11 72 19 29  8 32 93 43 47 51 52 56 62 66 69 30 17 68  8
0  5 33 11 72 19 29 30 32 93 43 47 51 52 56 62 66 69  8 17 68  8
0  5 33 11 72 19 29 30 32 93 43 47 51 52 56 62 66  8 69 17 68  8
0  5 33 11 72 19 29 30 32 93 43 47 51 52 56 62 66 68 69 17  8  8
0  5 33 11 72 19 29 30 32  8 43 47 51 52 56 62 66 68 69 17 93  8
0  5  8 11 72 19 29 30 32 33 43 47 51 52 56 62 66 68 69 72 93  0
0  5  8 11 17 19 29 30 32 33 43 47 51 52 56 62 66 68 69 17 93  0




5
1 5 3 4 2
7

4
4 3 2 1
10
*/
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
void input(FILE *file)
{
    long i,n,max,ave; INT16U *A, *B; char buffer[20];

    fgets(buffer, sizeof(buffer)-1, file);
    sscanf(buffer, "%ld", &n);
    A = malloc(succ(n)*sizeof(INT16U));
    B = malloc(succ(n)*sizeof(INT16U));
    for (i=ave=max=0; i<n; i++){
        fscanf(file, "%hd",  &A[i]);
        if (max<A[i])
            max=A[i];
        ave+=A[i];
    }
    ave/=n;
    C = malloc(succ(max)*sizeof(INT16U));
    memset(C, 0, sizeof(INT16U)*succ(max));
    CountingSort(A, B, n, max);
    printf("%ld\n", mincostsort(A, n));
#ifdef DESKTOP
    for (i=0; i<n; i++){
        if (i) printf(" ");
        printf("%hd", A[i]);
    }
    printf("\n");
#endif
    free(A);
    free(B);
    free(C);
}
//============================================================================
#ifndef DESKTOP
int main()
{
    input(stdin);
    return 0;
}
#endif