#include<stdio.h>
#include<limits.h>

int max(int a,int b)
{
    return(a > b?a:b);
}

void revArrCpy(int a[],int b[],int n)
{
    int i;
    for(i = 0;i < n;i++)
    b[n-i-1] = a[i];
}

int binSearchIndex(int a[],int low,int high,int x)
{
    while(low < high)
    {
        int mid = low + (high - low)/2;
        if(a[mid] < x)
        low = mid+1;
        else if(a[mid] > x)
        high = mid;
        else
        return mid;
    }

    return low;
}

void getLISArray(int a[],int lis[],int n)
{
    int i = 0,end[n];

    end[i] = a[0];
    int len = 0;
    lis[i] = len+1;

    for(i = 1;i < n;i++)
    {
        if(a[i] <= end[len])
        {
            int pos = binSearchIndex(end,0,len,a[i]);
            lis[i] = pos+1;
            end[pos] = a[i];
        }
        else{
            end[++len] = a[i];
            lis[i] = len+1;
        }
    }
}

void swap(int* a,int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void reverse(int a[],int n)
{
    int low = 0,high = n-1;
    while(low < high)
    {
        swap(a+low,a+high);
        low++;
        high--;
    }
}

void printArray(int a[],int n)
{
    int i;
    for(i = 0;i < n;i++)
    printf("%d ",a[i]);
    printf("\n");
}

int lbs(int a[],int n)
{
    int lis[n],lds[n],i;
    for(i = 0;i < n;i++)
    lis[i] = lds[i] = 1;

    getLISArray(a,lis,n);
    printArray(lis,n);
    int rev[n];
    revArrCpy(a,rev,n);
    getLISArray(rev,lds,n);
    reverse(lds,n);
    printArray(lds,n);

    int maximum = INT_MIN;
    for(i = 0;i < n;i++)
    maximum = max(maximum,lis[i]+lds[i]-1);

    return maximum;
}

int main()
{
    int a[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
    int n = sizeof(a)/sizeof(a[0]);
    printf("The LBS is %d\n",lbs(a,n));
    return 0;
}