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 <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <assert.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<pair<int, int> > A(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i].first;
		A[i].second = i;
	}
	sort(A.begin(), A.end());

	int x = -1;
	for (int i = 0; i < N; i++) {
		if (A[i].first >= N - i - 1) {
			x = i;
			break;
		}
	}
	//cerr <<"x = "  <<  x << endl;
	if (x == -1) {
		res = 0;
		for (int i = 0; i < N; i++) {
			res += abs(A[i].first - A[i].second);
		}
	}
	else {
		priority_queue<pair<int, int> > le;
		for (int i = 0; i < x; i++) {
			if (A[i].second < N - x) {
				le.emplace(-A[i].first - A[i].second - abs(A[i].first - A[i].second), i);
			}
		}

		priority_queue<pair<int, int> > ri;
		for (int i = x; i < N; i++) {
			if (A[i].second >= N - x) {
				ri.emplace(A[i].first + A[i].second - abs(A[i].first - A[i].second), i);
			}
		}
		//cerr << le.size() << " " << ri.size() << endl;
		//assert(le.size() == ri.size());
		for (int i = 0; i < M; i++) {
			if ((int)le.size() == 0)break;
			int X = le.top().second; le.pop();
			int Y = ri.top().second; ri.pop();

			swap(A[X].second, A[Y].second);
			//cerr << X << " " << Y << endl;

		}
		res = 0;
		for (int i = 0; i < N; i++) {
			res += abs(A[i].first - A[i].second);
		}

	}


	cout << res << endl;
}