菜鸡求助，不如暴力分qaq

#include<bits/stdc++.h>
#define MAXN 100005
#define MAXM 100005
#define inf (long long)4340410370284600380
#define reg register
#define inl inline
#define int long long
using namespace std;
deque <int> q;
int cnt=1,fst[MAXN<<1],nxt[MAXM],to[MAXM],w[MAXM],cot[MAXM],cur[MAXN<<1];
int n,W,a[MAXN],t[MAXN],S,T,dis[MAXN<<1],mincost,tot,sum;
bool inq[MAXN<<1],vis[MAXN<<1];
void AddEdge(reg int u,reg int v,reg int c,reg int fl)
{
	to[++cnt]=v;
	nxt[cnt]=fst[u];
	fst[u]=cnt;
	w[cnt]=c;
	cot[cnt]=fl;
}
inl bool Spfa()
{
	memset(dis,60,sizeof(dis));
	memset(inq,0,sizeof(inq));
	q.push_front(T);
	dis[T]=0;
	inq[T]=1;
	while(!q.empty())
	{
		reg int u=q.front();
		q.pop_front();
		inq[u]=0;
		for(reg int i=fst[u];i;i=nxt[i])
		{
			reg int v=to[i];
			if(dis[v]>dis[u]-cot[i] && w[i^1])
			{
				dis[v]=dis[u]-cot[i];
				if(!inq[v])
				{
					if(!q.empty() && dis[v]<dis[q.front()]) q.push_front(v);
					else q.push_back(v);
					inq[v]=1;
				}
			}
		}
	}
	return dis[S]!=inf;
}
int Dfs(reg int u,reg int flow)
{
	vis[u]=1;
	if(u==T || !flow) return flow;
	reg int used=0;
	for(reg int i=cur[u];i;i=nxt[i])
	{
		cur[u]=i;
		reg int v=to[i];
		if(dis[v]==dis[u]-cot[i] && w[i] && !vis[v])
		{
			reg int fl=Dfs(v,min(flow,w[i]));
			if(fl)
			{
				used+=fl;
				flow-=fl;
				w[i]-=fl;
				w[i^1]+=fl;
				if(!flow) break;
			}
		}
	}
	return used;
}
inl void zkwMCMF()
{
	while(Spfa())
	{
		vis[T]=1;
		while(vis[T])
		{
			memcpy(cur,fst,sizeof(fst));
			memset(vis,0,sizeof(vis));
			reg int fl=Dfs(S,inf);
			mincost+=dis[S]*fl;
		}
	}
}
void Link(reg int l,reg int r)
{
	if(l==r) return;
	reg int mid=l+r>>1,tot=0;
	Link(l,mid);
	Link(mid+1,r);
	for(reg int i=l;i<=r;i++) t[++tot]=a[i];
	sort(t+1,t+tot+1);
	tot=unique(t+1,t+tot+1)-t-1;
	for(reg int i=1;i<tot;i++)
	{
		AddEdge(i+sum,i+sum+1,inf,t[i+1]-t[i]);
		AddEdge(i+sum+1,i+sum,0,t[i]-t[i+1]);
		AddEdge(i+sum+1,i+sum,inf,t[i+1]-t[i]);
		AddEdge(i+sum,i+sum+1,0,t[i]-t[i+1]);
	}
	for(reg int i=l;i<=r;i++)
	{
		reg int pos=lower_bound(t+1,t+tot+1,a[i])-t;
		if(i<=mid)
		{
			AddEdge(pos+sum,i+n,1,0);
			AddEdge(i+n,pos+sum,0,0);
		}
		else
		{
			AddEdge(i,pos+sum,1,0);
			AddEdge(pos+sum,i,1,0);
		}
	}
	sum+=tot;
}
signed main()
{
	scanf("%lld %lld",&n,&W);
	S=0;
	T=n*2+1;
	sum=n*2+1;
	for(reg int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(reg int i=1;i<=n;i++)
	{
		AddEdge(S,i,1,0);
		AddEdge(i,S,0,0);
		AddEdge(i,T,1,W);
		AddEdge(T,i,0,-W);
		AddEdge(i+n,T,1,0);
		AddEdge(T,i+n,0,0);
	}
	Link(1,n);
	zkwMCMF();
	printf("%lld\n",mincost);
	return 0;
}