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

void sort(int x,int y,char *a)
{
    int xx=x,yy=y; 
    char k=a[x]; 
    if(x>=y)
        return ; 
    while(xx!=yy)
    {
         while(xx<yy&& a[yy]>=k)yy--;
         a[xx]=a[yy];
         while(xx<yy&& a[xx]<=k)xx++;
         a[yy]=a[xx];
    }
    a[xx]=k;
    sort(x,xx-1,a);
    sort(xx+1,y,a);
}

int main()
{
    char *a, *b, *c ,d[9];
    int i,j,k=0,n,N;
    while((a=(char *)malloc(sizeof(char)*100))==NULL);
    while((b=(char *)malloc(sizeof(char)*100))==NULL);
    while((c=(char *)malloc(sizeof(char)*100))==NULL);
    for(i=0;i<100;i++)
    {
        a[i]=0;
        b[i]=0;
        c[i]=0;
    }
    N=100;
    a[0]=1;
    b[0]=1;
    n=0;
    for(i=3;;i++)
    {
        for(j=0;j<=n;j++)
            c[j]=a[j]+b[j];
        for(j=0;j<=n;j++)
            if(c[j]>=10)
            {
                c[j+1]+=c[j]/10;
                c[j]%=10;
            }
        if(c[n+1]>0)
            n+=1;
        if(n>10)
        {
            for(j=0;j<9;j++)
                d[j]=c[j];
            sort(0, 8, d);
            for(j=0;j<9;j++)
                if(d[j]!=j+1)
                    break;
            if(j==9)
            {
                printf("last nine %d\n",i);
                k=1;
            }
            for(j=n;j>n-9;j--)
                d[n-j]=c[j];
            sort(0, 8, d);
            for(j=0;j<9;j++)
                if(d[j]!=j+1)
                    break;
            if(j==9)
            {
                printf("first nine %d\n",i);
                k+=1;
            }
            if(k==2)
            {
                printf("last and first nine %d\n",i);
                break;
            }
            else
                k=0;
        }
        if(n==N-1)
        {
            N+=100;
            free(a);
            a=NULL;
            while((a=(char *)malloc(sizeof(char)*N))==NULL);
            for(j=0;j<N-100;j++)
                a[j]=b[j];
            for(;j<N;j++)
                a[j]=0;
            free(b);
            b=NULL;
            while((b=(char *)malloc(sizeof(char)*N))==NULL);
            for(j=0;j<N-100;j++)
                b[j]=c[j];
            for(;j<N;j++)
                b[j]=0;
            free(c);
            c=NULL;
            while((c=(char *)malloc(sizeof(char)*N))==NULL);
            for(j=0;j<N;j++)
                c[j]=0;
        }
        else
        {
            for(j=0;j<=n;j++)
            {
                a[j]=b[j];
                b[j]=c[j];
                c[j]=0;
            }
        }
    }
    return 0;
}