Run O(nlogn)

#include<stdio.h>

int main()
{
    int n;
    scanf("%d",&n);
    int arr[n+1];
    int lis[n+1];
    for(int i = 1 ; i <= n ; i ++){
        scanf("%d",&arr[i]);
    }
    int maxa = 1;
    lis[1] = arr[1];
    int ansfor[n+1];
    ansfor[1] = 1;
    for(int i = 2 ; i <= n ; i++){
        if(arr[i] <= lis[1]){
            lis[1] = arr[i];
            ansfor[i] = 1;
        }
        else if(arr[i] > lis[maxa]){
            lis[++maxa] = arr[i];
            ansfor[i] = maxa;
        }
        else{
            int l = 1 , r = maxa - 1;
            int pos = 1;
            while(l <= r){
                int m = (l+r)/2;
                if(lis[m] < arr[i]){
                    pos = m;
                    l = m + 1;
                }
                else{
                    r = m - 1;
                }
            }
            lis[pos+1] = arr[i];
            ansfor[i] = pos + 1;
        }
    }/*
    for(int i = 1 ; i <= n ;i ++){
        printf("%d ",ansfor[i]);
    }
    printf("\n");
    */
    int arrrev[n+1];for(int i = n ; i >= 1 ; i --)arrrev[n - i + 1] = arr[i];
    int maxr = 1;
    int lisrev[n+1];
    int ansrev[n+1];
    lisrev[maxr] = arrrev[1];
    ansrev[1] = 1;
    for(int i = 1 ; i <= n ; i ++){
    //  printf("%d ",arrrev[i]);
        if(arrrev[i] <= lisrev[1]){
            lisrev[1] = arrrev[i];
            ansrev[i] = 1;
        }
        else if(arrrev[i] > lisrev[maxr]){
            lisrev[++maxr] = arrrev[i];
            ansrev[i] = maxr;
        }
        else{
            int l = 1 , r = maxr - 1;
            int pos = 1;
            while(l <= r){
                int m = (l+r)/2;
                if(lisrev[m] < arrrev[i]){
                    pos = m;
                    l = m + 1;
                }
                else{
                    r = m - 1;
                }
            }
            lisrev[pos+1] = arrrev[i];
            ansrev[i] = pos+1;
        }
    }
    int ansback[n+1];
    int ans = 1;
    for(int i = 1 ; i <= n ; i ++){
        ansback[i] = ansrev[n-i+1];
    //  printf("%d ",ansback[i]);
        int sum = ansfor[i] + ansback[i] - 1;
        if(sum > ans)ans = sum;
    }
    printf("%d",ans);
    return 0;
}