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;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template <typename T>
struct SegmentTree{
  using F = function<T(T,T)>;
  Int n;
  F f;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(F f,T ti):f(f),ti(ti){}
  void init(Int n_){    
    n=1;
    while(n<n_) n<<=1;
    dat.assign(n<<1,ti);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  void set_val(Int k,T x){
    dat[k+=n]=x;
    while(k>>=1)
      dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);    
  }
  T query(Int a,Int b){
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[l++]);
      if(r&1) vr=f(dat[--r],vr);
    }
    return f(vl,vr);
  }
  template<typename C>
  Int find(Int a,Int b,C &check,Int k,Int l,Int r){
    if(!check(dat[k])||r<=a||b<=l) return -1;
    if(k>=n) return k-n;
    Int m=(l+r)>>1;
    Int vl=find(a,b,check,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(a,b,check,(k<<1)|1,m,r);
  }
  template<typename C>
  Int find(Int a,Int b,C &check){
    return find(a,b,check,1,0,n);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> v(n);
  for(Int i=0;i<n;i++) cin>>v[i];
  Int ans=0;
  for(Int i=0;i<n;i++) ans+=abs(v[i]-i);
  
  using P = pair<Int, Int>;
  struct T{
    P a,b,c;
    T(){}
    T(P a,P b,P c):a(a),b(b),c(c){}
  };
  auto f=[&](T x,T y){
           return T(max(x.a,y.a),min(x.b,y.b),x.c);
         };

  vector<T> vt(n);
  for(Int i=0;i<n;i++){
    vt[i]=T(P(min(v[i],i),i),P(max(v[i],i),i),P(i,i));    
  }

  const Int INF = 1e9;
  T ti(P(-INF,-INF),P(INF,INF),P(0,0));
  SegmentTree<T> seg(f,ti);
  seg.build(vt);

  for(Int i=0;i<m;i++){
    T res=seg.query(0,n);
    Int x=res.b.second;
    Int y=res.a.second;
    if(x==y) break;
    if(min(v[y],y)<=max(v[x],x)) break;
    //cout<<x<<" "<<y<<endl;
    ans+=(min(v[y],y)-max(v[x],x))*2;
    swap(v[x],v[y]);
    vt[x]=T(P(min(v[x],x),x),P(max(v[x],x),x),P(x,x));
    vt[y]=T(P(min(v[y],y),y),P(max(v[y],y),y),P(y,y));
    seg.set_val(x,vt[x]);
    seg.set_val(y,vt[y]);
  }
  Int res=0;
  for(Int i=0;i<n;i++) res+=abs(v[i]-i);
  assert(ans==res);  
  //cout<<ans<<endl;
  cout<<res<<endl;
  
  return 0;
}