Problem: problem

Given a sequence $ A $ of length $ N $. You can swap the $ i $ th and $ j $ th ($ 0 \ leq i, j \ leq N-1 $) elements of a sequence up to $ M $ times.

Find the maximum value of $ \ sum_ {i = 0} ^ {N -1} abs (A_i --i) $ in the sequence created by the operation.



output

Find the maximum value of $ \ sum_ {i = 0} ^ {N --1} abs (A_i --i) $ in the sequence created by the operation. Also, output a line feed at the end.

Example

Input

5 2
0 3 2 1 4


Output

12

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
ll N, M;
ll A[100050];
int main() {
    ll ans = 0;
    cin >> N >> M;
    priority_queue<l_l> indexes;
    priority_queue<l_l> values;
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        ans += abs(i - A[i]);
        values.push({A[i], i});
        indexes.push({i, i});
    }
    values.push({-1, 0});
    indexes.push({-1, 0});
    priority_queue<ll> profit;
    priority_queue<ll, vector<ll>, greater<ll> > cost;
    for(int i = 1; i <= N; i++) {
        l_l now;
        //cerr << i << " " << values.top().first << " "<< indexes.top().first << endl;
        if(values.top() > indexes.top()) {
            now = values.top();
            values.pop();
            ll index = now.second;
            if(A[index] < index) profit.push(2 * A[index]);
        } else {
            now = indexes.top();
            indexes.pop();
            ll index = now.second;
            if(index <= A[index]) profit.push(2 * index);
        }
    }
    for(int i = 1; i <= N; i++) {
        l_l now;
        //cerr << i << " " << values.top().first << " "<< indexes.top().first << endl;
        if(values.top() > indexes.top()) {
            now = values.top();
            values.pop();
            ll index = now.second;
            if(A[index] >= index) cost.push(2 * A[index]);
        } else {
            now = indexes.top();
            indexes.pop();
            ll index = now.second;
            if(A[index] < index) cost.push(2 * index);
        }
    }
    //cerr << profit.size() << " " << cost.size() << endl;
    while(M--) {
        if(profit.empty()) break;
        ll PROFIT = profit.top();
        profit.pop();
        ll COST = cost.top();
        cost.pop();
        //cout << PROFIT << " " << COST << endl;
        ans += PROFIT - COST;
    }
    cout << ans << endl;
}