#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> struct median_priority_queue { std::priority_queue<T> pqL; std::priority_queue<T, std::vector<T>, std::greater<T>> pqR; median_priority_queue() { //pqL.emplace(std::numeric_limits<T>::min()); //pqR.emplace(std::numeric_limits<T>::max()); } void push(T v){ if(!pqL.empty() && v < pqL.top()) pqL.emplace(v); else pqR.emplace(v); update(); } T get(){ return pqR.top(); } int size(){ return int(pqL.size() + pqR.size()); } void update(){ while(pqL.size() + 2 <= pqR.size()){ pqL.emplace(pqR.top()); pqR.pop(); } while(pqL.size() > pqR.size()){ pqR.emplace(pqL.top()); pqL.pop(); } } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n), b(n), parent(n); vector<median_priority_queue<int>> pq(n); for(auto &&v : a) cin >> v; sort(a.begin(), a.end()); iota(parent.begin(), parent.end(), 0); function<int(int)> leader = [&](int v){ return v == parent[v] ? v : parent[v] = leader(parent[v]); }; auto merge = [&](int i, int j){ if(pq[i].size() < pq[j].size()){ swap(pq[i], pq[j]); swap(i, j); } parent[j] = i; auto &tmp = pq[j].pqR; while(!tmp.empty()){ pq[i].push(tmp.top()); tmp.pop(); } auto &tmp2 = pq[j].pqL; while(!tmp2.empty()){ pq[i].push(tmp2.top()); tmp2.pop(); } }; stack<int> st; for(int i = 0; i < n; i++){ b[i] = a[i] - i; pq[i].push(b[i]); st.emplace(i); } for(int i = 0; i + 1 < n; i++){ if(b[i] == b[i + 1]) merge(i, i + 1); } while(st.size() >= 2){ int i = leader(st.top()); st.pop(); int j = leader(st.top()); if(i == j) continue; if(pq[j].get() > pq[i].get()) merge(i, j); } for(int j = 0; j < 30; j++){ st.pop(); for(int i = 0; i < n; i++){ st.emplace(i); } while(st.size() >= 2){ int i = leader(st.top()); st.pop(); int j = leader(st.top()); if(i == j) continue; if(pq[j].get() > pq[i].get()) merge(i, j); } } ll ans = 0; for(int i = 0; i < n; i++){ ans += abs(b[i] - pq[parent[leader(i)]].get()); } cout << ans << '\n'; }