You are given $n$ integers $w_i (i = 0, 1, ..., n-1)$ to be sorted in ascending order. You can swap two integers $w_i$ and $w_j$. Each swap operation has a cost, which is the sum of the two integers $w_i + w_j$. You can perform the operations any number of times.

Write a program which reports the minimal total cost to sort the given integers.

Constraints

* $1 \leq n \leq 1,000$
* $0 \leq w_i\leq 10^4$
* $w_i$ are all different

Input

In the first line, an integer $n$ is given. In the second line, $n$ integers $w_i (i = 0, 1, 2, ... n-1)$ separated by space characters are given.

Output

Print the minimal cost in a line.

Examples

Input

5
1 5 3 4 2


Output

7


Input

4
4 3 2 1


Output

10
#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];
    // C holds position of A
    // C[A[val]] = pred val position

    /*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, A[i],
                            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);
}
//----------------------------------------------------------------------------
void prnary(INT16U *A, INT16U N)
{
    int j;

    for (j=0; j<N; j++)
        printf("%2d ", A[j]);
    printf(" sum:%ld\n", sum);
}
//----------------------------------------------------------------------------
short linklen(INT16U *A, INT16U N, INT16U val)
{
    int idx,n;


    for (n=0, idx=val; ; n++){
        idx=A[pred(C[idx])];
        if (idx==val)
            return n;
    }
}
//----------------------------------------------------------------------------
void duplication(INT16U *A, INT16U N)
{
    int i,j,k,n,a,ary[3];

#ifdef DESKTOP
    prnary(A, N);
#endif
    for (i=sum=0; i<pred(N); i++){
        n=linklen(A, N, A[i]);
        if (n==1){
            j=pred(C[A[i]]);
            exchange(&A[i], &A[j]);
            printf("ex:(%d<->%d), ", A[i], A[j]);
        }else
        if (n==2){
            ary[0]=i;
            ary[1]=pred(C[A[i]]);
            ary[2]=pred(C[A[ary[1]]]);
            for (j=a=0,k=20000; j<3; j++)
            if (A[ary[j]]<k){
                k=A[ary[j]];
                a=ary[j];
            }
            j=pred(C[A[a]]);
            k=pred(C[A[j]]);
            if (A[j]<A[k]){
                //printf("ex:(%d<->%d), ", A[a], A[k]); // 44<>96
                exchange(&A[a], &A[k]);
            }else{
                //printf("ex:(%d<->%d), ", A[a], A[j]); // 44<>96
                exchange(&A[a], &A[j]);
            }
            //printf("ex:(%d<->%d), ", A[k], A[j]); // 44<>96
            exchange(&A[k], &A[j]);
        }
#ifdef DESKTOP
    }
    printf("\n");
#else
    }
#endif
}
//----------------------------------------------------------------------------
long mincostsort(INT16U *A, INT16U N)
{
    int ptr,i,j,min,ordptr,order[100];

    duplication(A, N);
    for (i=0,j=32000; i<N; i++)
        if (A[i]<j)
            j=A[i],min=i;
    for (ordptr=0; 0<=(ptr=getminptr(A, N));){
#ifdef DESKTOP
    printf("[%d]\n", A[ptr]);
#endif
        order[ordptr++]=A[ptr];
        if (A[min]*2<A[ptr]){
            exchange(&A[min], &A[ptr]);
            min=ptr;
        }
        while (pred(C[A[ptr]])!=ptr){
            for (i=0; i<N; i++)
                if (C[A[i]]==succ(ptr)){
                    order[ordptr++]=A[i];
                    if (ptr==min) min=i;
                    exchange(&A[ptr], &A[i]);
                    ptr=i;
#ifdef DESKTOP
                    //prnary(A, N);
#endif
                    break;
                }
        }
    }
#ifdef DESKTOP
    for (i=0; i<ordptr; i++){
        if (i) printf("->");
            printf("%d", order[i]);
    }
    printf("\n");
#endif
    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

 1 80 50 70 40 20
20 80 50 70 40  1
20  1 50 70 40 80
 1 20 50 70 40 80 21        20 40 50 70  1 80   41
40 20 50 70  1 80 41        20 40 50  1 70 80   71
40 20 50  1 70 80 71        20 40  1 50 70 80   51
40 20  1 50 70 80 51        20  1 40 50 70 80   41
 1 20 40 50 70 80 41         1 20 40 50 70 80   21


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