#include <fstream>
#include <iostream>
#include <vector>
#define N 100005
using namespace std;

ifstream fin("balba.in");
ofstream fout("balba.out");
int v[N], fv[12], k;
int s[N], sol[N];

void palindrom1(int cif)
{
  int i,j;
  k=0;
  for(i=9; i>=0; --i)
    if(!(i==0 && k==0))
    {
      if(i==cif)s[++k]=i;
      for(j=1; j<=fv[i]/2; j++)s[++k]=i;
    }

  for(i=9; i>=0; i--)
    if(fv[i]%2==1)
    {
      s[++k]=i;
      break;
    }
  for(i=0; i<=9; i++)
    if(!(i==0 && k<=1))
    {
      for(j=1; j<=fv[i]/2; j++)
        s[++k]=i;
    }
}

void palindrom2(int cif)
{
  int i,j;
  k=0;
  for(i=9; i>=0; --i)
    if(!(i==0 && k==0))
    {
      for(j=1; j<=fv[i]/2; j++)s[++k]=i;
    }
  for(i=9; i>=0; --i)
    if(fv[i]%2==1)
    {
      s[++k]=i;
      break;
    }
  for(i=0; i<=9; ++i)
    if(!(i==0 && k<=1))
    {
      if(i==cif) s[++k]=i;
      for(j=1; j<=fv[i]/2; j++)
        s[++k]=i;
    }
}

int main()
{
  int cer,n,i,k1=0, k2=0,cif,ok=0,l;
  fin>>cer>>n;
  for(i=1; i<=n; i++)fin>>v[i];
  if(cer==1)
  {
    for(i=1; i<=n; i++)
    {
      l=1;
      while(i<n && v[i]==v[i+1]) i++,l++;
      k1++;
      if(l>=2)k2++;
    }
    fout<<k1<<"\n"<<k2;
  }
  else ///cer 2
  {
    for(i=1; i<=n; i++) fv[v[i]]++;
    palindrom1(-1);
    for(int i=1; i<=k; i++)sol[i]=s[i];
    l=k;
    palindrom2(-1);
    if(k>l)
    {
      l=k;
      for(i=1; i<=k; ++i)sol[i]=s[i];
    }
    else if(k==l)
    {
      ok=0;
      for(i=1; i<=k; ++i)
        if(sol[i]!=s[i])
        {
          if(sol[i]<s[i]) ok=1;
          break;
        }
      if(ok==1)
      {
        for(i=1; i<=k; ++i)
          sol[i]=s[i];
      }
    }
    ///pe cifre
    for(cif=0; cif<=9; cif++)
      if(fv[cif]>=3)
      {
        fv[cif]--;
        palindrom1(cif);
        if(k>1)
        {
          l=k;
          for(i=1; i<=k; ++i)sol[i]=s[i];
        }
        else if(k==1)
        {
          ok=0;
          for(i=1; i<=k; ++i)
            if(sol[i]!=s[i])
            {
              if(sol[i]<s[i])ok=1;
              break;
            }
          if(ok==1)
          {
            for(i=1; i<=k; ++i)sol[i]=s[i];
          }
        }
        palindrom2(cif);
        if(k>l)
        {
          l=k;
          for(i=1; i<=k; i++)sol[i]=s[i];

        }
        else if(k==l)
        {
          ok=0;
          for(i=1; i<=k; i++)
            if(sol[i]!=s[i])
            {
              if(sol[i]<s[i])ok=1;
              break;
            }
          if(ok==1)
          {
            for(i=1; i<=k; i++)sol[i]=s[i];
          }
        }
        fv[cif]++;
      }
    for(i=1; i<=l; i++)
      fout<<sol[i];
  }

  return 0;
}