#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int dr = 1;
int best[1000] = {0};

void citire( int *n, int **vector)
{
    int i, j;
    int *sir;

    FILE *f = fopen( "scmax.in","rt");

    if( f == NULL){
        printf( "Fisierul nu poate fi deschis!!!");
        exit(0);
    }

    fscanf(f, "%i", n);
    //printf("{este%i}\n",*n);
    sir = (int*)calloc(*n+1, sizeof(int));

    for( i = 1; i <= *n; i++)
        fscanf(f,"%i", &sir[i]);

    *vector = sir;

    fclose( f);

    return;
}

void afisare(int n, int *vector)
{
    int i;

    printf("\n");
    for( i = 0; i < n; i++)
        printf(" %i", vector[i]);

    return;
}

int cauta( int curent, int n, int *vector, int *L, int* p)
{
    int i = 1, j, dr_temp = dr;
    int st = 1,mij, m_mare;

    //metoda de cautare binara
    if(vector[curent]<= vector[L[dr]])
        do
        {
            m_mare = 0;
            mij = (st+dr_temp)/2;
            //printf(" curent:%i,vector[curent]:%i, mij:%i, vector[L[mij]]:%i\n",curent, vector[curent],mij, vector[L[mij]]);
            if(vector[curent]<vector[L[mij]]){
                //printf("mai mic");
                dr_temp = mij;
            }
            else
             if(vector[curent]==vector[L[mij]])
             {
                  //printf("Elementul a fost gasit pe pozitia %i",mij);
                  //ok=1;
                  //printf("egal");
                  break;
             }
             else{
                 //printf("mai mare");
                 m_mare = 1;
                 st = mij+1;
             }

             //getch();
         }while(st<dr_temp);
    else
        mij = dr;

    //printf(" i_ret= %i ",mij);
    if(m_mare){ dr = ++mij; return mij;}
    //trebuie pus si p - de cine se leaga elementul curent

    return mij;
}

int afis_rec( int poz, int *vector, int *p, FILE *f)
{
    //printf( " poz: %i", poz);
    //getch();
    if( poz != 0){
        afis_rec( p[poz], vector, p, f);

        fprintf( f, " %i", vector[poz]);
    }

    return 1;
}
int main()
{
    int i, j, n, m, curent, max = 0;
    int *vector, *p, *L, poz = 0, *best;
    FILE *f = fopen( "scmax.out", "wt");

    citire( &n, &vector);

    p = (int*)calloc(n, sizeof(int));//de cine se leaga
    best = (int*)calloc(n, sizeof(int));//cel mai lung subsir crescator
    L = (int*)calloc(n, sizeof(int));//cel mai recent numar de lungime i

    best[1] = 1;
    curent = 2;
    L[1] = 1;L[2]=1;

    //cel mai lung sir este best[i-1]
    //caut elementul curent
    while( curent <= n){

        poz = cauta(curent, n, vector, L, p);
        L[poz] = curent;
        p[curent] = L[poz - 1];
        best[curent] = poz;
        printf("\nL:");
        for(j=1;j<=dr;j++)
            printf(" %i->%i",j,L[j]);
        //printf("\n");
        //best[curent] = i;

        //    break;

        curent++;
    }

    afisare( n, vector);
    afisare( n, p);
    afisare( n, best);
    afisare( n, L);

    max = best[1]; poz = 1;
    for(i = 2; i < curent; i++)
        if(best[i] > max){ max = best[i]; poz = i;}

    printf("\n poz: %i, max: %i \n",poz,max);
    fprintf( f, "%i\n", max);

    afis_rec( poz, vector, p, f);

    fclose( f);
    return 0;
}