Kada ste uspešno pomogli Dragančetu da brzo reši zadatak Gaus, profesor Đurić se stvarno naljutio i rešio da za sledeći čas smisli stvarno težak zadatak. Profesor Đurić je sav srećan došao sutradan u školu, i dao đacima sledeći zadatak. Na tabli je napisao niz brojeva, i traži da pronađu najkraći niz čiji su elementi brojeva iz skupa {1, 2, ..., n-1, n} (pri čemu se u nizu mogu ponavljati isti brojevi) koji nije podniz niza napisanog na tabli. Sva deca su se umirila i profesor Đurić je sedeo zadovoljno, očekujući da je miran bar za sledećih nekoliko godina. Ali prevideo je dve male stvari: da je mali Draganče pametniji od ostale dece, a i da se druži sa vama, dobrim programerima. Draganče misli da je smislio način da nađe dužinu traženog niza, ali ne i koji je to niz, pa vas je zato pozvao u pomoć. Prvo treba da nađete dužinu tog niza, da bi Draganče proverio svoje rešenje, a zatim ne bi bilo loše ni da nađete taj niz. Da li će profesor Đurić ponovo biti ljut, ostaje na vama da se vidi.

Ulaz:

(Ulazni podaci se nalaze u datoteci podniz.in) U prvom redu nalaze se dva broja, n i m, gde je m broj elemenata niza zapisanog na tabli. Brojevi napisani na tabli i brojevi u traženom (pod)nizu su iz skupa {1, 2, ..., n-1, n}. U sledećih m redova nalazi se po jedan broj i oni predstavljaju brojeve zapisane na tabli.

Izlaz:

(Izlazne podatke upisati u datoteku podniz.out) U prvom redu napisati k - broj elemenata traženog niza. U sledećih k redova napisati redom po jedan element traženog niza. Ako ima više nizova iste dužine, napisati onaj koji je prvi leksikografski. Niz b je podniz niza a ako postoji niz t tako da za svako i važi b(i) = a(t(i)), t(i) < t(i+1) (dakle, niz b se može dobiti od niza a izbacivanjem nekih elemenata). Tj. od niza 1213 podnizovi su npr. 12, 23, 123, a nisu 31, 22. Za tačno izračunat broj k dobija se 40% poena na tom test primeru.

Ograničenja:

• n, m ≤ 1000000
• vremensko ograničenje za izvršavanje programa je 1 s.

Napomena:

U jezicima C/C++ koristite biblioteku stdio, a ne iostream, jer iostream-u treba više od 1 sekunde da učita 1000000 brojeva.

Primer 1:

2 3
1
2
1

2
2
2

Primer 2:

2 4
1
2
2
1

3
1
1
1

Primer 3:

3 10
1
2
3
3
2
1
1
2
3
1

4
1
1
2
2

#include <stdio.h>
#include <time.h>
#include <memory.h>

const int maxn = 1100000;

int a[maxn],ozn[maxn],d[maxn];

int main()
{
    int start = clock();
    freopen("podniz.in","r",stdin);
    freopen("podniz.out","w",stdout);
    
    int n,m;
    scanf("%d%d",&n,&m);
    
    int i,j,k,t;
      
    for(i= 0;i<m;i++)
    {
       scanf("%d",&(a[i]));
       a[i]--;
    }
    memset(ozn,0,n*sizeof(ozn[0]));
    
    k = 1; t = 0;
    for(i = m-1;i>=0;i--)
    {
        d[i] = k; 
        if (ozn[a[i]]==0)
        {
            ozn[a[i]] = 1;
            t++;
            if (t==n)
            {               
               memset(ozn,0,n*sizeof(ozn[0]));
               t=0;
               k++;
            }            
        }     
    }
    
    int res = k;
    printf("%d\n",res);
    
    memset(ozn,0,n*sizeof(ozn[0]));
    for(i = 0;i<m;i++)
    {
       if (d[i]!=k)
       {
           for (j = 0;(j<n)&&(ozn[j]);j++);
           printf("%d\n",j+1);
           k--;
           if (k==0) break;
           for (;(i<m)&&(j!=a[i]);i++);
           memset(ozn,0,n*sizeof(ozn[0]));         
       }                 
       else ozn[a[i]]=1; 
    }
    
    if (k==1) 
    {
       for (j = 0;(j<n)&&(ozn[j]);j++);
       printf("%d\n",j+1);
    }        
        
    return 0;   
}

var a,ozn,d:array[0..1100000] of Longint;
    fin,fout:Text;
    n,m,i,j,k,t,res:Longint;
    ind:boolean;
begin


    Assign(fin,'podniz.in');
    reset(fin);
    Assign(fout,'podniz.out');
    rewrite(fout);

    readln(fin,n,m);




    for i:=0 to m-1 do
    begin
       readln(fin,a[i]);
       a[i]:=a[i]-1;
    end;
    fillchar(ozn, n*sizeof(a[0]), 0);


    k := 1; t := 0;
    for i := m-1 downto 0 do
    begin
        d[i] := k;
        if (ozn[a[i]]=0) then
        begin
            ozn[a[i]] := 1;
            t:=t+1;
            if (t=n) then
            begin
               fillchar(ozn, n*sizeof(a[0]), 0);
               t:=0;
               k:=k+1;
            end;
        end;
    end;

    res := k;
    writeln(fout,res);
    ind:=true;
    fillchar(ozn, n*sizeof(a[0]), 0);
    i:=0;
    while (i<m) and ind do
    begin
       if (d[i]<>k) then
       begin
           j := 0;
     while ((j<n)and(ozn[j]>0)) do
      j:=j+1;
     writeln(fout,j+1);
           k:=k-1;
           if (k=0) then
             ind :=false
           else while ((i<m)and(j<>a[i])) do i:=i+1;
           fillchar(ozn, n*sizeof(a[0]), 0);
       end
       else ozn[a[i]]:=1;
       i:=i+1;
    end;

    if (k=1) then
    begin
       j := 0;
       while ((j<n)and(ozn[j]>0)) do j:=j+1;
       writeln(fout,j+1);
    end;

    close(fin);
    close(fout);
end.