#include using namespace std; using ll = long long; template struct median_priority_queue { std::priority_queue pqL; std::priority_queue, std::greater> pqR; median_priority_queue() { //pqL.emplace(std::numeric_limits::min()); //pqR.emplace(std::numeric_limits::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 a(n), b(n), parent(n); vector> pq(n); for(auto &&v : a) cin >> v; sort(a.begin(), a.end()); iota(parent.begin(), parent.end(), 0); function 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 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 < 10; 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'; }