1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 100000000000 13 #define maxn 200000 14 #define eps 1e-10 15 #define ll long long 16 #define pa pair<int,int> 17 #define for0(i,n) for(int i=0;i<=n;i++) 18 #define for1(i,n) for(int i=1;i<=n;i++) 19 #define for2(i,x,y) for(int i=x;i<=y;i++) 20 using namespace std; 21 inline int read() 22 { 23     int x=0,f=1;char ch=getchar(); 24     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 25     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 26     return x*f; 27 } 28 int fa[maxn],c[maxn][2],n,k,a[maxn],tot=0,rt=0,v[maxn]; 29 ll sum[maxn],s[maxn]; 30 inline void pushup(int x) 31 { 32     int l=c[x][0],r=c[x][1]; 33     s[x]=s[l]+s[r]+1; 34     sum[x]=sum[l]+sum[r]+v[x]; 35 } 36 inline void rotate(int x,int &k) 37 { 38     int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 39     if(y==k)k=x;else c[z][c[z][1]==y]=x; 40     fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 41     c[y][l]=c[x][r];c[x][r]=y; 42     pushup(y);pushup(x); 43 } 44 inline void splay(int x,int &k) 45 { 46     while(x!=k) 47      { 48          int y=fa[x],z=fa[y]; 49          if(y!=k) 50           { 51               if(c[z][0]==y^c[y][0]==x)rotate(x,k);else rotate(y,k); 52           } 53          rotate(x,k);  54      } 55 } 56 inline void ins(int &k,int kk,int x) 57 { 58     if(!k) 59     { 60         k=++tot;s[tot]=1;fa[tot]=kk;v[tot]=sum[tot]=x;return; 61     } 62     s[k]++; 63     if(x<=v[k])ins(c[k][0],k,x);else ins(c[k][1],k,x); 64     pushup(k); 65 } 66 inline int find(int k,int x) 67 { 68     int l=c[k][0],r=c[k][1]; 69     if(s[l]+1==x)return k; 70     else if(s[l]>=x)return find(l,x); 71     else return find(r,x-s[l]-1);  72 } 73 inline int pos(int k,int val) 74 { 75     if(v[k]==val)return k; 76     else if(val<v[k])return pos(c[k][0],val); 77     else return pos(c[k][1],val); 78 } 79 inline void del(int val) 80 { 81     splay(pos(rt,val),rt); 82     int x=c[rt][0],y=c[rt][1]; 83     while(c[x][1])x=c[x][1]; 84     while(c[y][0])y=c[y][0]; 85     splay(x,rt);splay(y,c[x][1]); 86     fa[c[y][0]]=c[y][0]=0; 87     pushup(y);pushup(x); 88 } 89 int main() 90 { 91     freopen("input.txt","r",stdin); 92     freopen("output.txt","w",stdout); 93     n=read();k=read(); 94     for1(i,n)a[i]=read();  95     ins(rt,0,-1);ins(rt,0,1000001); 96     for1(i,k-1)ins(rt,0,a[i]),splay(i+2,rt); 97     ll ans=inf,x,y; 98     for1(i,n-k+1) 99      {100          ins(rt,0,a[i+k-1]);splay(i+k+1,rt);101          x=find(rt,(s[rt]>>1)+1);y=v[x];102          splay(x,rt);103         ans=min(ans,s[c[x][0]]*y-sum[c[x][0]]+sum[c[x][1]]-s[c[x][1]]*y);104         del(a[i]);105         if(ans==1000002)break;106      }107     printf("%lld\n",ans-1000002);     108     return 0;109 }