#include<iostream>
#include<stdio.h>

#define INF 10000000
#define MAXN 101000
#define FOR(i,l,r) for (i=l;i<=r;i++)
#define NX(i) ((i==n)?1:(i+1))
#define LX(i) ((i==1)?n:(i-1))
#define D1(i,j) ((i>=j)?(i-j):(INF-j+i))
#define D2(i,j) ((i==j)?0:((i>j)?(INF-i+j):(j-i)))

using namespace std;
int i,j,k,l,m,n;
long long ans=(long long)(INF)*INF;
static int a[MAXN];
void solve() {
     int i,j,k,o1=1,o2=1,u1=0,u2=0;
     long long tot=0;
     for (;D2(a[LX(o1)],a[1])<=D1(a[LX(o1)],a[1]);o1=LX(o1),tot+=(long long)(D2(a[o1],a[1])),u1++);
     for (;D2(a[NX(o2)],a[1])>D1(a[NX(o2)],a[1]);o2=NX(o2),tot+=(long long)(D1(a[o2],a[1])),u2++);
     FOR(i,1,n) {
        ans=min(ans,tot);
        if (i==n) break;
        if (o2==i) {o2=NX(o2);tot+=(long long)(n-1)*D1(a[NX(i)],a[i])-D2(a[o1],a[i]);o1=NX(o1);}
        for (tot-=(u2?D1(a[NX(i)],a[i])*(long long)(u2--):0);D2(a[NX(o2)],a[i+1])>D1(a[NX(o2)],a[i+1]);) {
            o2=NX(o2);tot+=(long long)(D1(a[o2],a[i+1]));u2++;
        }
        for (tot+=(u1!=n-1?D1(a[NX(i)],a[i])*(long long)(++u1):0);D2(a[o1],a[i+1])>D1(a[o1],a[i+1]);) {
            tot-=(long long)(D2(a[o1],a[i+1]));o1=NX(o1);u1--;
        }
     }
     printf("%I64d\n",ans);
}

void qs(int l,int r) {
     int i=l,j=r,k=a[(l+r)/2];
     while (i<=j) {
           for (;a[i]<k;i++);
           for (;k<a[j];j--);
           if (i<=j) swap(a[i++],a[j--]);
     }
     if (i<r) qs(i,r);
     if (j>l) qs(l,j);
}

int main() {
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
    qs(1,n);solve();
    return 0;
}