#include <algorithm>
#include <iostream>
#include <numeric>
constexpr int N(200010),inf(1.01e9);
namespace T
{
	struct _z
	{
		int mn,mnc,tg;
	}z[N<<2];
	void add(int u,int v)
	{
		z[u].mn+=v;z[u].tg+=v;
	}
	void pd(int u)
	{
		if(z[u].tg) add(u<<1,z[u].tg),add(u<<1|1,z[u].tg),z[u].tg=0;
	}
	void pu(int u)
	{
		if(z[u<<1].mn<z[u<<1|1].mn) z[u].mn=z[u<<1].mn,z[u].mnc=z[u<<1].mnc;
		else if(z[u<<1].mn>z[u<<1|1].mn) z[u].mn=z[u<<1|1].mn,z[u].mnc=z[u<<1|1].mnc;
		else z[u].mn=z[u<<1].mn,z[u].mnc=z[u<<1].mnc+z[u<<1|1].mnc;
	}
	void build(int u,int cl,int cr)
	{
		if(cl==cr){z[u].mn=inf;z[u].mnc=1;return;}int mid((cl+cr)>>1);
		build(u<<1,cl,mid);build(u<<1|1,mid+1,cr);pu(u);
	}
	void upd(int u,int cl,int cr,int ql,int qr,int v)
	{
		if(cl>=ql && cr<=qr){add(u,v);return;}else if(cl!=cr) pd(u);int mid((cl+cr)>>1);
		if(ql<=mid) upd(u<<1,cl,mid,ql,qr,v);if(qr>mid) upd(u<<1|1,mid+1,cr,ql,qr,v);pu(u);
	}
}
long long slv(int a[],int n)
{
	T::build(1,1,n);static int smx[N],smn[N];int tmx(0),tmn(0);
	long long ans(0);
	for(int i(1);i<=n;++i)
	{
		//mx-mn+l
		while(tmn && a[smn[tmn]]>a[i])
		{
			T::upd(1,1,n,smn[tmn-1]+1,smn[tmn],a[smn[tmn]]);
			--tmn;
		}
		smn[++tmn]=i;
		T::upd(1,1,n,smn[tmn-1]+1,smn[tmn],-a[smn[tmn]]);
		while(tmx && a[smx[tmx]]<a[i])
		{
			T::upd(1,1,n,smx[tmx-1]+1,smx[tmx],-a[smx[tmx]]);
			--tmx;
		}
		smx[++tmx]=i;
		T::upd(1,1,n,smx[tmx-1]+1,smx[tmx],a[smx[tmx]]);
		T::upd(1,1,n,i,i,-inf+i);
		if(T::z[1].mn==i) ans+=T::z[1].mnc;
	}
	return ans;
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n,k;std::cin>>n>>k;
	static int a[N],vs[N],b[N];for(int i(1);i<=k;++i) std::cin>>a[i],vs[i]=a[i];std::sort(vs+1,vs+k+1);
	for(int i(1);i<=k;++i) b[i]=std::lower_bound(vs+1,vs+k+1,a[i])-vs;
	if(!k) std::iota(a+1,a+n+1,1);
	else
	{
		int pos(k);
		vs[0]=0;vs[k+1]=n+1;int bl(b[k]),br(b[k]),tl(b[k]),tr(b[k]);
		auto radd=[&](int r,int l)->void{for(int i(r);i>=l;--i) a[++pos]=i;};
		auto add=[&](int l,int r)->void{for(int i(l);i<=r;++i) a[++pos]=i;};
		int cntl(1),cntr(1);
		auto chg=[&]()->void
		{
			if(cntl>=cntr)
			{
				if(tl>bl) radd(vs[tl]-1,vs[tl-1]+1);
				if(tr<br) add(vs[tr]+1,vs[tr+1]-1);
			}
			else
			{
				if(tr<br) add(vs[tr]+1,vs[tr+1]-1);
				if(tl>bl) radd(vs[tl]-1,vs[tl-1]+1);
			}
			for(int i(tr+1);i<br;++i) add(vs[i]+1,vs[i+1]-1);
			for(int i(tl-1);i>bl;--i) radd(vs[i]-1,vs[i-1]+1);
			if(tl==bl) ++cntl;else cntl=1;if(tr==br) ++cntr;else cntr=1;
			tl=bl;tr=br;
		};
		for(int i(k-1);i;--i)
		{
			bl=std::min(bl,b[i]),br=std::max(br,b[i]);
			if(br-bl==k-i)
			{
				chg();
			}
		}
		bl=0;br=n+1;
		chg();
		std::cout<<slv(a,n)<<"\n";
		for(int i(1);i<=n;++i) std::cout<<a[i]<<(" \n"[i==n]);
	}
	return 0;
}