#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 2010100

int n;
int cnt[sz];

ll ww[sz];

#define ls k<<1
#define rs k<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
int tr1[sz<<2]; ll tr2[sz<<2];
void modify(int k,int l,int r,int x,int w) {
    tr1[k]+=w,tr2[k]+=w*ww[x];
    if (l==r) return;
    int mid=(l+r)>>1;
    if (x<=mid) modify(lson,x,w);
    else modify(rson,x,w);
}
pair<int,ll> query(int k,int l,int r,int x) {
    if (tr1[k]<=x) return {tr1[k],tr2[k]};
    if (l==r) return {x,x*ww[l]};
    int mid=(l+r)>>1;
    auto L=query(lson,x);
    if (L.fir==x) return L;
    auto R=query(rson,x-L.fir);
    return {L.fir+R.fir,L.sec+R.sec};
}
void debug(int k,int l,int r) {
    if (l==r) {
        rep(_,1,tr1[k]) cerr<<ww[l]<<' ';
        return;
    }
    int mid=(l+r)>>1;
    debug(lson),debug(rson);
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    ll sum=0;
    rep(i,1,n) {
        int x; cin>>x;
        if (x>n) sum+=x-n,x=n;
        ++cnt[x];
    }
    const ll inf=2e12;
    priority_queue<ll,vector<ll>,greater<ll>>q1,q2;
    rep(i,1,n) {
        if (q1.size()) {
            ll t=q1.top(); q1.pop();
            ww[i]=-t-i-i;
            q2.push(ww[i]);
        }
        else q2.push(-i-inf),ww[i]=-i-inf;
        rep(_,1,cnt[i]) {
            if (q2.size()&&q2.top()+i<0) {
                ll t=q2.top(); q2.pop();
                q1.push({-t-i-i});
            }
            else q1.push({-i});
        }
    }
    rep(i,1,n) ww[i+n]=-i;
    sort(ww+1,ww+2*n+1);
    int res1=n; ll res2=0;
    rep(i,1,n) res2+=1ll*i*cnt[i];
    while (q1.size()) q1.pop();
    while (q2.size()) q2.pop();
    auto id=[](ll w) {
        return lower_bound(ww+1,ww+2*n+1,w)-ww;
    };
    ll ans=1e18;
    rep(i,1,n) {
        if (q1.size()) {
            ll t=q1.top(); q1.pop();
            sum+=t+i;
            q2.push(-t-i-i);
            modify(1,1,n*2,id(-t-i-i),1);
        }
        else sum+=inf,q2.push(-i-inf),modify(1,1,n*2,id(-i-inf),1);
        rep(_,1,cnt[i]) {
            if (q2.size()&&q2.top()+i<0) {
                ll t=q2.top(); q2.pop();
                modify(1,1,n*2,id(t),-1);
                sum+=t+i;
                q1.push({-t-i-i});
            }
            else q1.push({-i});
        }
        res1-=cnt[i],res2-=1ll*i*cnt[i];
        // priority_queue<ll,vector<ll>,greater<ll>>q3=q2;
        // ll cur=sum+res2;
        // rep(_,1,res1) {
        //     if (q3.size()&&q3.top()<-i) cur+=q3.top(),q3.pop();
        //     else cur+=-i;
        // }
        // chkmin(ans,cur);
        modify(1,1,n*2,id(-i),n);
        // debug(1,1,2*n);
        // cerr<<'\n';
        ll cur=sum+res2;
        auto www=query(1,1,2*n,res1);
        cur+=www.sec;
        modify(1,1,n*2,id(-i),-n);
        chkmin(ans,cur);

        // debug(1,1,2*n);
        // cerr<<'\n';
        // auto q3=q2;
        // while (q3.size()) cerr<<q3.top()<<' ',q3.pop();
        // cerr<<'\n';
    }
    cout<<ans<<'\n';
    return 0;
}