#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)
	{
		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;vs[k+1]=n+1;
	if(!k) std::iota(a+1,a+n+1,1);
	else
	{
		int pos(k);
		static int ls[N],rs[N];int cnt(1);int bl(b[k]),br(b[k]);ls[1]=-b[k];rs[1]=b[k];
		// std::cerr<<vs[bl]<<" "<<vs[br]<<std::endl;
		for(int i(k-1);i;--i)
		{
			bl=std::min(bl,b[i]);br=std::max(br,b[i]);
			if(br-bl==k-i) ++cnt,ls[cnt]=-bl,rs[cnt]=br/*,std::cerr<<vs[bl]<<" "<<vs[br]<<std::endl*/;
		}
		struct _q
		{
			bool rev;
			int pos,st,ed,v;
		};
		static _q qs[N];int q(0);
		auto chk=[](int l,int r)->bool{return vs[r]-vs[l]==r-l;};
		for(int i(b[k]);i<=k;++i)
		{
			int l(std::lower_bound(rs+1,rs+cnt+1,i)-rs),r(std::upper_bound(rs+1,rs+cnt+1,i)-rs);
			if(l==r) qs[++q]=(_q){false,l-1,vs[i]+1,vs[i+1]-1,-i};
			else
			{
				int mx(0),mp(0);
				for(int j(l),t;j<r;j=t)
				{
					for(t=j;t<r && chk(-ls[t],-ls[j]);++t);
					int cur(t-j);
					if(j>l && chk(-ls[j],-ls[j-1]-1)) ++cur;
					if(cur>mx)
					{
						mx=cur;
						mp=t-1;
					}
				}
				qs[++q]=(_q){false,mp,vs[i]+1,vs[i+1]-1,mx};
			}
		}
		for(int i(b[k]);i;--i)
		{
			int l(std::lower_bound(ls+1,ls+cnt+1,-i)-ls),r(std::upper_bound(ls+1,ls+cnt+1,-i)-ls);
			if(l==r) qs[++q]=(_q){true,l-1,vs[i]-1,vs[i-1]+1,-N+i};
			else
			{
				int mx(0),mp(0);
				for(int j(l),t;j<r;j=t)
				{
					for(t=j;t<r && chk(rs[j],rs[t]);++t);
					int cur(t-j);
					if(j>l && chk(rs[j-1]+1,rs[j])) ++cur;
					if(cur>mx)
					{
						mx=cur;
						mp=t-1;
					}
				}
				qs[++q]=(_q){true,mp,vs[i]-1,vs[i-1]+1,mx};
			}
		}
		std::sort(qs+1,qs+q+1,[](auto a,auto b)->bool{if(a.pos!=b.pos) return a.pos<b.pos;return a.v>b.v;});
		for(int i(1);i<=q;++i)
		{
			if(qs[i].rev)
			{
				for(int j(qs[i].st);j>=qs[i].ed;--j) a[++pos]=j;
			}
			else
			{
				for(int j(qs[i].st);j<=qs[i].ed;++j) a[++pos]=j;
			}
		}
	}
	std::cout<<slv(a,n)<<"\n";
	for(int i(1);i<=n;++i) std::cout<<a[i]<<(" \n"[i==n]);
	return 0;
}