#include #define Re register int const int N=4e6+105; int i,j,n,m,h=1,t=0,T,ti,ans=2e9,G[N],S[N],Q[N],dp[N]; inline int min(Re a,Re b){return aY(i)?2e9:-2e9):(long double)(Y(j)-Y(i))/(long double)(X(j)-X(i));} int main(){ scanf("%d%d",&n,&m); for(i=1;i<=n;T=-min(-T,-ti),++G[ti],S[ti]+=ti,++i)scanf("%d",&ti); for(i=1;i=slope(Q[t-1],i-m+1))--t; Q[++t]=i-m+1;//(j+1)+m<=i } for(i=T;i